Tasowanie kart i teoria grup
Przyjrzyjmy się pewnej znanej technice tasowania. Talię kart dzielimy na połowy i przeplatamy je w taki sposób, że karty jednej połowy talii są poprzedzielane kartami drugiej. Oczywiście zazwyczaj ani podział ani tasowanie nie są idealne. Rozważmy jednak sytuację idealną, która jest bardziej interesująca dla matematyków, sztukmistrzów i szulerów. Łatwo wykazać, że niezależnie od wielkości talii, tasując ją wielokrotnie w ten sposób, po pewnym czasie powrócimy do pierwotnego układu kart. Czas, po jakim powrócimy zależy od wielkości talii: dla talii złożonej z 12 kart nastąpi to po 10 powtórzeniach, ale dla talii złożonej z 32 kart już po pięciu. A jak to jest dla zwykłej talii 52 kart?
Na razie, aby lepiej śledzić co się dzieje z kartami, rozważmy talię złożoną z 8 kart: 1, 2, 3, ..., 8. Przy podziale na połowy i idealnym przeplataniu, początkowy układ daje dwie dwie możliwości:
(12345678) → (12345678) albo (13572468) → (24681357)
My założymy, że splatamy według schematu przedstawionego po lewej stronie, tzn. tak, że zawsze pierwsza i ostatnia karta pozostają na swoim miejscu (karty zewnetrzne pozostają zewnętrzne, dlatego takie tasowanie nazywa się tasowaniem zewnetrznym). Prześledźmy, co dzieje się z kartą drugą. Po pierwszym spleceniu przejdzie ona na pozycję 3 i dalej zachowuje się tak, jakby była kartą trzecią. Tak więc po dwu spleceniach znajdzie się na pozycji 5, a po trzech spleceniach powróci na pozycję 2. Tak więc karty 2, 3 oraz 5 będą przesuwać się cyklicznie:
2 → 3 → 5 → 2
Podobnie jest z kartami 4, 6 oraz 7:
4 → 7 → 6 → 4.
Widzimy więc, że po trzech przeplotach każda karta powróci na swoje miejsce.
Dla dużej talii te obliczenia są dość czasochłonne. Ciekawe, że można je znacznie uprościć przenumerowując karty. Zamiast numeracji 1- 8 zastosujmy numerację 0 - 7. Wówczas rozważane przez nas tasowanie odpowiada następującemu przestawieniu kart:
(01234567) → (02461357)
Pomińmy siódemkę, o której i tak wiemy, że przechodzi na siebie. Dla pozostałych kart to, co dzieje się z kartą o numerze n przy jednokrotnym przepleceniu talii, można zapisać wzorem:
n → 2n (mod 7).
Dla liczby naturalnej m napis m (mod 7) oznacza resztę z dzielenia liczby m przez 7.
W przypadku zwykłej talii 52 kart możemy postąpić podobnie. Karty numerujemy od 0 do 51. Karta 51 przejdzie na samą siebie, a dla pozostałych kart mamy wzór
n → 2n (mod 51)
Karta 0 (pierwsza od góry) przechodzi po każdym przeplocie na siebie. Koleje karty 1 (drugiej od góry) wyglądają następująco:
1→ 2→ 4→ 8→ 6→ 32→ 13 → 26 → 1.
Widzimy, że karta numer 1 powraca na swoje miejsce po 8 przeplotach. Można sprawdzić, że to samo dotyczy pozostałych kart. Tej żmudnej pracy można jednak uniknąć, korzystając z podanego wzoru. Położenie karty n po każdym kroku otrzymujemy mnożąc jej aktualne położenie przez 2 (mod 51). Mamy zatem:
Po pierwszym kroku n → 2n (mod 51)
Po drugim kroku n → 4n (mod 51)
Po trzecim kroku n → 8n (mod 51)
..................................................................
Po ósmym kroku n → 256n (mod 51)
Zauważmy, że 256 n = 255 n+n = 5·51 n+n = n (mod 51). Zatem dla ustalenia, po ilu krokach każda karta przechodzi na siebie, wystarczyło znaleźć najmniejszą liczbę k taką, że 2k=1 (mod 51).
Tasowanie kart opisaną techniką to z matematycznego punktu widzenia wielokrotne składanie permutacji
P : (12345...505152) → (13579...485052)
Pytanie, po ilu tasowaniach powrócimy do pierwotnego ułożenia kart to pytanie, jaka jest najmniejsza liczba naturalna n, dla której Pn=I.
Zadania
1. Po ilu krokach powrócimy do pierwotnego układu, przy idealnym tasowaniu talii złożonej z:
a) 12 kart; b) 14 kart; c) 16 kart; d) 24 kart; e) 30 kart?
2. Po ilu krokach powróci do pierwotnego ułożenia talia złożona z 2n kart?
3. Jak wyglądają analogiczne obliczenia w przypadku tasowania wewnętrznego - w którym pierwsza i ostatania karta za każdym razem stają się drugą i przedostatnią kartą?