Trzynaście kart – rozwiązanie zagadki

https://xpil.eu/9gg 📋

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?

https://xpil.eu/9gg 📋