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 k_i-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 k_i-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

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ő.

Már regisztráltál?
Új vendég vagy?