Cím: Szalonpóker: kártyakeverés és kongruenciák
Szerző(k):  Hraskó András ,  Jelitai Árpád 
Füzet: 2005/szeptember, 325 - 327. oldal  PDF  |  MathML 
Témakör(ök): Egyéb írások
Hivatkozás(ok):Feladatok: 2005/szeptember: B.3841

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.

A Matematika Határok Nélkül ezévi versenyén szerepelt az alábbi feladat:

 
Szalonpóker. Little John és Old Firehand betérnek Black Jacky híres kaszinójába egy kártyapartira. A játékhoz egy 1-től 32-ig megszámozott 32 lapos kártyacsomagot használnak. Mielőtt megbeszélnék a játékszabályokat, Black Jacky összekeveri a kártyákat az alábbi módon. Leteszi az asztalra a kártyapaklit, leveszi a fölső 16 lapot, s megfordítás nélkül a maradék pakli jobb oldalára helyezi. Ekkor úgy keveri össze a két paklit, hogy egymás után hol az egyik, hol a másik pakli egy-egy lapja kerül egymásra a bal oldali pakli alsó lapjával elkezdve a keverést (a bal oldali pakli alsó lapja marad alul, 1. ábra). Az így összekevert paklit összefogja, majd ugyanezt többször megismételve folytatja az eljárást. Little John biztos benne, hogy ez nem egy tisztességes keverési mód. Mutassátok meg, hogy többször megismételve az eljárást, meglepő eredmény adódik.
 
 

1. ábra
 

 

111111217953232179534182513745321795619102111674182513782026291589532179102111619101161910211112222714231213741825131423122227141582026291516242830311617953217182513741819102111619202629158202111619102122271423122223122227142324283031162425137418252629158202627142312222728303116242829158202629303116242830311624283031323232323232
 

A meglepő eredmény az, hogy ötszöri keverés után visszakapjuk a kártyalapok eredeti sorrendjét. A mellékelt táblázat hat oszlopában megadtuk, hogy az öt keverési lépés során hogyan alakul a lapok sorrendje.
Jogosan merül fel a kérdés, hogy vajon miért éppen az ötödik keverés után kapjuk vissza az eredeti sorrendet, sőt, már az sem nyilvánvaló, hogy a feladatban leírt keverési lépések ismételgetésével ilyesmire egyáltalán sor kerül. Foglalkozzunk először az utóbbi kérdéssel.
Egy keverés az 1,2,...,32 számok egy permutációjának tekinthető. Mivel a permutációk száma véges, előbb vagy utóbb szükségszerű az ismétlődés. A legelső ismétlődés pedig csak a lapok eredeti sorrendje lehet, mert különböző permutációkból a megadott keverés alkalmazásával különbözőket kapunk. Ezért a legelső ismétlődéskor nem kaphatunk vissza olyan permutációt, amit egy másikból már megkaptunk.
Az első kérdésre adott választ leegyszerűsíti, ha a kongruenciák nyelvén fogalmazunk.
Emlékeztetünk a jól ismert definícióra: ha m>1 egész szám, akkor két egész számról azt mondjuk, hogy kongruensek modulo m, ha különbségük osztható m-mel. Jelölése:
a≡b(modm),ham∣a-b(a,  b,  m  egész számok).
Adott m modulusra vonatkozó kongruencia reláció hasonló tulajdonságokkal rendelkezik, mint az egyenlőség, így például
a≡a(reflexív)a≡b→b≡a(szimmetrikus)a≡b,b≡c→a≡c(tranzitív)a≡b→a+c≡b+c,ac≡bc.

Nézzük most az eredeti feladatot. A leírt keverés során a legfelső és a legalsó lap a helyén marad. A többiek nyomonkövetéséhez számozzuk át a lapokat; a felső 16 lap számozása 0-tól 15-ig, az alsó lapok számozása 16-tól 31-ig változik. Vizsgáljuk meg, hogy a k-adik helyen álló lap (0≤k≤31) egy keverés során melyik helyre kerül. Legyen ez k1 (0≤k1≤31). Ha k≤15, akkor a fölötte álló lapok száma k-val növekszik (az alsó részből ennyi lap kerül fölé), tehát k1=2k. Ha 16≤k, akkor a mögötte álló lapok száma (31-k)-val növekszik, ennyivel csökken az előtte álló lapok száma, tehát az új helyének sorszáma k1=k-(31-k)=2k-31. Így két különböző képlet szerint változik a lapok helyének a sorszáma, attól függően, hogy a pakli alsó vagy felső részében van-e a kártyalap. Ha viszont a kongruenciák nyelvén fogalmazunk, akkor nem kell megkülönböztetni a két lehetőséget: egységesen k1≡2k(mod31). Most már ugyanígy folytathatjuk: az újabb keverés után k1-edik helyen álló lap arra a k2-edik helyre kerül, amelyre k2≡2k1≡22k(mod31), és így tovább...
Az ötödik keverés után tehát a k-adik helyről arra a k5-ödik helyre kerül a kártyalap, amelyre
k5≡25k=32k≡k(mod31),mert32≡1(mod31).
Az 1≤k5≤31 feltétel figyelembevételével azt kapjuk, hogy k5=k, tehát az ötödik keverés után valóban minden lap visszakerül az eredeti helyére.