Trzynaście kart – rozwiązanie zagadki

Zagadka jest wbrew pozorom dość prosta, o ile tylko dysponujemy komputerem oraz odrobiną pomyślunku.

Trzynaście kart można ułożyć na 13! = 6 227 020 800 różnych sposobów. Sześć miliardów z hakiem to nie tak dużo, o ile tylko powiemy komputerowi jak ma sprawdzać każdy układ i zostawimy go z tym problemem na jakiś czas.

Kłopot pojawia się przy większych taliach, ponieważ silnia jest wredna i rośnie naprawdę szybko. W przypadku talii złożonej z 52 kart na policzenie tego najszybszymi znanymi obecnie komputerami trzeba by było czekać tryliony lat. Trochę przydługo. Jednak matematycy to szczwane bestie i potrafią czasem obejść takie tematy boczkiem. Udało się już na przykład ustalić, że maksymalna liczba odwróceń w talii 52-elementowej wynosi *mniej więcej* 4012. Dowodu – póki co – nie ma.

Żeby policzyć maksymalną ilość liczbę odwróceń, trzeba wygenerować wszystkie możliwe potasowania i dla każdego z nich policzyć, po ilu odwróceniach dostaniemy na górze jedynkę.

W tym celu napiszemy sobie dwanaście linii kodu w Pythonie:

from itertools import permutations
talia = list(range(1,14))
najlepszy = 0
for p in permutations(talia):
    odwrocenia = 0
    uklad = list(p)
    while uklad[0] != 1:
        uklad[0:uklad[0]] = uklad[0:uklad[0]][::-1]
        odwrocenia += 1
    if odwrocenia > najlepszy:
        najlepszy = odwrocenia
        print(odwrocenia, p)

Powyższy kod wykonywał się na moim domowym komputerze około piętnastu godzin. Okazało się, że maksymalna ilość liczba odwróceń to 80. Kombinację, która daje 80 odwróceń, program znalazł po mniej więcej półtora godzinie, ale trzeba było sprawdzić pozostałe układy, stąd tak długi czas wykonania całości.

Krótkie omówienie kodu dla zainteresowanych:

from itertools import permutations daje nam możliwość wyznaczania wszystkich permutacji podanej listy.

talia = list(range(1,14)) – generujemy listę trzynastu liczb i zapamiętujemy ją w zmiennej talia.

najlepszy = 0 – zmienna najlepszy zapamiętuje najlepszy aktualny wynik (czyli maksymalną dotychczas znalezioną ilość liczbę odwróceń).

for p in permutations(talia): – generujemy wszystkie permutacje (czyli wszystkie możliwe potasowania) talii.

Następnie, dla każdego potasowania:

– Zerujemy ilość liczbę odwróceń odwrocenia = 0
– Zapamiętujemy bieżące potasowanie w zmiennej uklad
– Dopóki na górze talii nie ma jedynki while uklad[0] != 1:, odwracamy tyle kart, ile wynosi wartość górnej karty uklad[0:uklad[0]] = uklad[0:uklad[0]][::-1] i zwiększamy licznik odwróceń o jeden odwrocenia += 1.
– Otrzymawszy na górze talii jedynkę, sprawdzamy czy udało nam się uzyskać więcej odwróceń, niż dotychczas if odwrocenia > najlepszy: i jeżeli tak, zapamiętujemy nowy rekord najlepszy = odwrocenia i wyświetlamy go na ekranie wraz z potasowaniem, które do niego doprowadziło print(odwrocenia, p).

W ten sposób na wyjściu uzyskamy listę kolejnych rekordów wraz z odpowiadającymi im potasowaniami:

1 (2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
2 (2, 3, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
3 (2, 3, 4, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13)
4 (2, 3, 4, 5, 1, 6, 7, 8, 9, 10, 11, 12, 13)
5 (2, 3, 4, 5, 6, 1, 7, 8, 9, 10, 11, 12, 13)
6 (2, 3, 4, 5, 6, 7, 1, 8, 9, 10, 11, 12, 13)
7 (2, 3, 4, 5, 6, 7, 8, 1, 9, 10, 11, 12, 13)
8 (2, 3, 4, 5, 6, 7, 8, 9, 1, 10, 11, 12, 13)
9 (2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 11, 12, 13)
10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 12, 13)
11 (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 13)
12 (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1)
14 (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 1, 12)
39 (2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 1, 12, 11)
40 (2, 3, 4, 5, 6, 7, 8, 10, 1, 11, 12, 13, 9)
46 (2, 3, 4, 5, 6, 7, 8, 10, 1, 12, 13, 9, 11)
47 (2, 3, 4, 5, 6, 7, 10, 9, 13, 8, 1, 12, 11)
52 (2, 3, 4, 5, 6, 7, 10, 12, 1, 11, 13, 9, 8)
54 (2, 3, 4, 5, 6, 9, 12, 1, 11, 13, 7, 10, 8)
55 (2, 3, 4, 5, 6, 10, 7, 12, 1, 11, 13, 8, 9)
57 (2, 3, 4, 5, 6, 10, 8, 12, 1, 11, 13, 7, 9)
60 (2, 3, 4, 5, 6, 11, 7, 13, 12, 10, 8, 1, 9)
66 (2, 3, 4, 5, 8, 1, 13, 11, 12, 10, 7, 6, 9)
68 (2, 3, 4, 6, 7, 11, 9, 13, 5, 12, 8, 1, 10)
69 (2, 3, 4, 6, 11, 7, 5, 13, 12, 1, 8, 9, 10)
73 (2, 3, 4, 10, 1, 5, 9, 13, 12, 8, 11, 6, 7)
74 (2, 3, 4, 10, 1, 8, 12, 13, 9, 5, 11, 6, 7)
75 (2, 3, 11, 1, 4, 5, 8, 13, 12, 10, 9, 7, 6)
77 (2, 4, 5, 11, 3, 10, 1, 8, 12, 13, 9, 6, 7)
80 (2, 9, 4, 5, 11, 12, 10, 1, 8, 13, 3, 6, 7)

Jak widać, układ (2, 9, 4, 5, 11, 12, 10, 1, 8, 13, 3, 6, 7) jest tym, przy którym trzeba karty przełożyć aż 80 razy, aby trafić na jedynkę – i jest to maksymalna ilość liczba przełożeń dla trzynastu kart.

Niewykluczone, że istnieją inne potasowania, które również dają 80 przełożeń – jednak jestem zbyt leniwy, aby to sprawdzić. Może któryś z Czytelników zechce to zrobić w wolnej chwili?

6
Dodaj komentarz

avatar
2 Comment threads
4 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
xpilWaldekxpilToni Recent comment authors
  Subscribe  
najnowszy najstarszy oceniany
Powiadom o
Toni
Gość

Zerknąłem, jak obiecałem, chociaż już powinienem iść spać, bo rano pobudka o 3:30.
Zaciekawił mnie tytuł ale ze zgrozą stwierdziłem, że nie jestem ani na tyle mądry w komputerze (zupełnym laikiem też nie) ani w matematyce. Zdradzę w tajemnicy, że nie wiem jak skończyłem szkołę podstawową (nie tylko) ponieważ do dziś nie opanowałem całej tabliczki mnożenia.
Tak czy inaczej bardzo ciekawy post.

Waldek
Gość
Waldek

„Okazało się, że maksymalna ilość odwróceń to 80”.
Hm, wydaje mi się, że minimalna „ilość odwróceń” to alef zero, więc maksymalna nie może być od niej mniejsza…