Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 3841. feladat (2005. szeptember)

B. 3841. Határozzuk meg, hogy ha a Szalonpóker cikkben leírt módon 52 lapot keverünk össze, akkor hányadik keverés után kapjuk vissza az eredeti sorrendet. Oldjuk meg ezt a feladatot abban az esetben is, ha a jobboldali pakli alsó lapjával kezdjük a keverést, vagyis ha az eredetileg 26-odik helyen álló kártya kerül a legalsó helyre.

Javasolta: Hraskó András és Jelitai Árpád, Budapest

(4 pont)

A beküldési határidő 2005. október 17-én LEJÁRT.


Megoldás. A cikkben leírt eljáráshoz hasonlóan számozzuk a lapokat felülről lefelé haladva a 0,1,2,\ldots, 51 számokkal. Az i-edik keverés után a k-adik lap arra a ki-edik helyre kerül, amelyre k_i\equiv 2^ik \pmod{51}. Az egyes sorszámú lap (fölülről tehát a második) pontosan akkor kerül a helyére, ha 2^i\equiv 1 \pmod{51}. Ekkor viszont már az összes többi lap is a helyére fog kerülni, hiszen csak két lapnak ugyanaz a sorszáma modulo 51 (az alsó és a fölső lapnak), de ezek végig helyben maradnak. Kettő hatványait modulo 51 egymás után felírva: 2,4,8,16,32,13,26,1,\ldots láthatjuk, hogy i=8 az a legkisebb szám, amelyre ez megvalósul, vagyis a nyolcadik keverés után áll vissza először az eredeti sorrend.

A másik esetben akkor tudjuk könnyen nyomon követni a kártyák mozgását, ha a lapokat 1-től 52-ig számozzuk. Ekkor az i-edik keverés után a k-adik lap arra a ki-edik helyre kerül, amelyre k_i\equiv 2^ik \pmod{53}. Most egyáltalán nincs két olyan lap, amelynek a sorszáma megegyezne modulo 53, tehát most azt a legkisebb i pozitív egész számot keressük, amelyre 2^i\equiv 1 \pmod{53}. A kettő hatványait ezúttal tehát modulo 53 írva fel: 2,4,8,16,32,11,\ldots elég sokáig kell azonban várnunk, amíg az 1 először felbukkan. Meggyorsíthatja a számolást, ha leszűkítjük azon i számok körét, amelyek szóba jöhetnek. Mivel 53 prímszám, a kis Fermat-tétel szerint 2^{52}\equiv 1
\pmod{53}. A periodicitást figyelembe véve, keresett i számunk szükségképpen 52-nek osztója, vagyis csak 1,2,4,13,26 vagy 52 lehet. Az első három értékről könnyen látszik, hogy nem jó. A 13-as kitevőt gyorsan így vizsgálhatjuk:

2^8\equiv 16^2\equiv 44\equiv -9 \pmod{53},

ahonnan

2^{13}=2^8\cdot 2^4\cdot 2\equiv (-9)\cdot 16\cdot 2=(-144)\cdot 2
\equiv 15\cdot 2=30 \pmod{53}.

Ez tehát még nem jó érték. Mivel pedig

2^{26}=(2^{13})^2\equiv 30^2\equiv (-23)^2=529\equiv -1 \pmod{53},

levonhatjuk a következtetést, miszerint az eredeti sorrend először az ötvenkettedik keverés után áll vissza. Ez tehát egy fokkal becsületesebb keverési módszer.


Statisztika:

137 dolgozat érkezett.
4 pontot kapott:59 versenyző.
3 pontot kapott:29 versenyző.
2 pontot kapott:38 versenyző.
1 pontot kapott:9 versenyző.
0 pontot kapott:2 versenyző.

A KöMaL 2005. szeptemberi matematika feladatai