Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 3841. (September 2005)

B. 3841. The problem below appears in the article ``Szalonpóker'' (Hungarian title) of the current issue. Suppose that a deck of 52 cards is suffled in the same way. How many times does it need to be shuffled in order to get back the initial order. Solve the problem for that case, too, when the shuffling starts with the bottom card of the deck on the right, that is, when the card in the 26th place originally is put at the bottom of the new deck.

(Little John and Old Firehand drop in the famous casino of Black Jacky to play cards. They play with a deck of 32 cards numbered 1 to 32. Before they agree on the rules, Black Jacky shuffles the cards as follows: He places the deck on the table, removes the top 16 cards and puts them on the table, to the right of the remaining deck without turning over. Then he forms one deck of them, with the bottom card of the deck on the left lying at the bottom, followed by alternating cards from the two decks. Then he repeats the procedure several times with the deck obtained in this way. Little John is sure that this way of shuffling the cards is not fair. Show that repeating the procedure several times will lead to a surprising result.)

(4 pont)

Deadline expired on October 17, 2005.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

137 students sent a solution.
4 points:59 students.
3 points:29 students.
2 points:38 students.
1 point:9 students.
0 point:2 students.

Problems in Mathematics of KöMaL, September 2005