Feladat: B.3889 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Almási Gábor András ,  Csaba Ákos ,  Csató László ,  Csige Péter ,  Csima Géza ,  Dudás László ,  Károlyi Gergely ,  Károlyi Márton ,  Kiss Réka ,  Kovács Péter ,  Kozma Márton ,  Kurgyis Eszter ,  Lovász László Miklós ,  Mercz Béla ,  Papp Máté ,  Pesti Veronika ,  Sümegi Károly ,  Szalóki Dávid ,  Szőke Nóra ,  Tomon István ,  Udvari Balázs ,  Varga László ,  Varga Péter 
Füzet: 2006/október, 413 - 415. oldal  PDF file
Témakör(ök): Többszemélyes véges játékok, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):Feladatok: 2006/február: B.3889

Egy bűvésztől láttam a következő mutatványt. Egy néző véletlenszerűen kiválasztott 5 lapot az 52 lapos francia kártyából, és átadta őket a bűvész segédjének. (A segéd a bűvész állandó partnere volt, így korábban már megállapodhattak.) A segéd megnézte az 5 lapot, és a bűvésznek egyesével átadott közülük 4-et. Ezután a bűvész ‐ anélkül, hogy bármi egyéb információt kapott volna ‐ megnevezte az ötödik lapot.
A mutatvány végeztével a bűvész az alábbi módon próbálta meggyőzni a matematika iránt érdeklődő nézőket:
,,A segítőm négy kártyát mutatott nekem, és ez a négy kártya tetszőlegesen kerülhet ki a pakliból. Információt tehát kizárólag a kártyák bemutatásának a sorrendjén keresztül közölhetett velem. Mint ismeretes, 4 kártyát 4!=24-féleképpen lehet sorbarendezni, az ötödik lap azonban 52-4=48-féle lehetett. Éppen 1 bit információ hiányzik tehát, ennek a pótlásához kell a csoda.''
Igaz-e, hogy a mutatványhoz valóban természetfölötti képességekre van szükség?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. A mutatvány végrehajtásához természetesen nincs szükség természetfölötti képességekre. Az alábbiakban megadunk két, legalábbis részben különböző módszert az ötödik lap meghatározására.

 
1. módszer. A francia kártya lapjai négyféle színűek lehetnek, az öt kártya között tehát vannak azonos színűek. Az első kártya segítségével a segéd így közölheti az utolsónak hagyott kártya színét: megállapodhat a bűvésszel, hogy az utolsó, ötödik lap ugyanolyan színű lesz majd, mint az első.
Az egyes színeken belül számozzuk meg a lapokat a szokásos módon 1-től 13-ig: Ász: 1, Kettes: 2, ..., Tízes: 10, J: 11, Q: 12, K: 13. Ha az utolsónak átadandó lap sorszáma x, az elsőé pedig y, akkor az első és az ötödik lap színe azonos, azért 1xy13. Megmutatjuk, hogy előzetes megállapodás után a második, harmadik és negyedik lap segítségével a segéd közölhet annyi információt, hogy a bűvész az y ismeretében meg tudja határozni x értékét és így magát az utolsó kártyalapot is.
Vegyük észre, hogy ha a színeket is rangsoroljuk, mondjuk a bridzsben szokásos treff, káró, kőr, pikk erősség szerint növekvően, és azonos színű lapok között a fenti számozást vesszük figyelembe, akkor bármely két kártyalap sorrendje egyértelműen eldönthető. Egy ilyen, úgynevezett lexikografikus rendezésben ‐ amelyben a segéd és a bűvész jóelőre megállapodhatnak ‐ a középső három kártyalap 3!=6-féle sorrendben adható át, a segéd tehát 6-féle információt, vagyis megfelelő előzetes megállapodás szerint egy 1 és 6 közé eső s egész számot közölhet a bűvésszel. Az y és az s segítségével próbálhatja meg a segéd a bűvésszel tudatni x értékét.
Hatféle szám ehhez kevésnek látszik, hiszen az y ismeretében az x még 12-féle értéket vehet föl. Első ránézésre egyáltalán nem világos, miképpen csökkenthető a felére a lehetőségek száma. Azon múlik a dolog, hogy a segéd a két egyszínű kártyalap közül eldöntheti, melyiket adja át elsőnek és melyiket utoljára, így pedig megfelelő előzetes megállapodás után ezzel is közölhet információt. Egy lehetőség a következő.
Legyen a két szélsőnek választott egyszínű kártyalap számértéke a és b, ahol a<b. Ekkor 1b-a12, különböztessünk meg tehát két esetet aszerint, hogy ez a különbség kisebb-e 7-nél (ez hat lehetőség) vagy pedig nem (ez is hat lehetőség). Az első esetben legyen y=a és s=b-a, végül x=b, a másodikban pedig legyen y=b, s=13-(b-a) és x=a. Mindkét esetben nyilván 1s6, továbbá x, tehát az ötödiknek átadott kártyalap számértéke éppen az y+s összeg maradéka 13-mal osztva.
Úgy is fogalmazhatjuk a dolgot, hogy ha a kártyalapok számozását ciklikusan folytatjuk mod 13, tehát például a 14-es is Ászt jelent, a 15-ös Kettest, és így tovább, akkor a két érték, a és b egyikéhez legfeljebb 6-ot adva megkapjuk a másik lap számértékét ‐ esetleg 13-mal eltolva. Ha a segéd ezt a lapot adja át elsőnek, akkor a következő három lap sorrendjével közölheti s értékét a bűvésszel, aki az y+s összeg 13-as maradékát kiszámolva megkapja az ötödik lap x számértékét.
 
2. módszer. Ha az első négy között van egy azonosítható ,,viszonyítási kártyalap'', akkor a leírt ciklikus számozás ötletével közvetlenül is a felére csökkenthető a lehetőségek száma. A fenti rendezés alapján például a kártyalapok megszámozhatók az 1-től 52-ig terjedő egész számokkal, Treff Ász: 1-től Pikk Király: 52-ig. Az első négy átadott lapnak a fenti rendezésben 4!=24-féle sorrendje van, ezt kihasználva s 1-től 24-ig bármilyen egész szám lehet. A négy átadott kártyalapon kívül 48 lehetőség van, ezek egyikét kell azonosítani az s 24-féle értéke segítségével.
A feleknek tehát csak abban kell megállapodniuk, hogy hogyan ismeri föl a bűvész ezt a ,,viszonyítási kártyalapot''. Legyen ez a négy, adott sorrendben átadott kártyalap közül a legnagyobb sorszámú. Ez nem függ a négy lap átadásának a sorrendjétől, ezzel a sorrenddel tehát a segéd nyugodtan közölheti az s értékét. Ha az öt lap számozása a1<a2<a3<a4<a5, akkor ismét két esetet különböztetünk meg. Ha a5-a424, akkor legyen az a5 az utoljára hagyott lap. Ekkor ha s=a5-a4, a trükk sikerül, hiszen a bűvész ki tudja választani a4-et, mint a négy átadott lap legnagyobbikát, a négy lap sorrendje alapján pedig megkapja s értékét. Ha pedig a5-a425, akkor a rendezés miatt a5-a128 és így a legnagyobb és a legkisebb kártyalap ciklikus távolsága, s=a1+52-a524. Ekkor a segéd az a1-et hagyja a végére, a bűvész pedig a5 és s értékéből megkapja a1-et, mint az a5+s összeg maradékát 52-vel osztva.