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

6 komentarzy

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

    1. I bardzo dobrze! Dzięki temu, że nie wszyscy (jeszcze) opanowali tajniki programowania komputerów, ciągle jeszcze mam pracę 🙂

      Zapraszam do działów tematycznych (w menu na górze), a nuż coś ciekawego się znajdzie?

  2. “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…

      1. Trochę głupio wymądrzać się u gospodarza tak sympatycznego bloga, lecz mimo to będę się upierał, że i zero, i 80 to liczby, a nie ilości. Matematycy o tym wiedzą, lecz i humaniści nie są gorsi. Cytat z poradni językowej PWN:
        “Słowa liczba i ilość nie powinny być używane zamiennie. Liczba dotyczy czegoś, co można policzyć, ilość – czegoś, czego się policzyć nie da”.

        1. Wcale nie tak głupio! O ile angielskie “much” i “many” opanowałem dość szybko i raczej się z ich używaniem nie mylę na co dzień, o tyle o rozróżnieniu między liczbą a ilością dowiedziałem się, wstyd przyznać, calkiem niedawno. I jeszcze mi ono nie weszło w krew. Dlatego należy mi to wytykać, żebym sobie utrwalił materiał 😉

          P.S. już poprawiam…

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.