Mieszamy trzynastoma kartami (zagadka)

https://xpil.eu/wjb

Dziś zagadka niebanalna. Osoby o niewykształconym gruczole kombinatorycznym proszone są o opuszczenie blogu i przejście na peron siódmy, skąd za chwilę odjeżdża pociąg do Joe Monstera, Nowego Pompona i Hacker News.

Dla tych z Was, którzy ośmielili się pozostać, oto zagadka:

Mamy talię trzynastu kart, ponumerowanych od jeden do trzynaście, po jednej liczbie na kartę. Dla ułatwienia liczba jest wydrukowana na obydwu stronach każdej karty (nie ma awersu - rewersu, każda karta wygląda tak samo po obu stronach).

Tasujemy naszą liczbową talię, następnie kładziemy ją w stos ("kupkę") przed nami i zaczynamy następującą zabawę:

  • Podnosimy ze stosu tyle kart, ile wynosi liczba na samej górze stosu (jest to jedyna liczba, którą widzimy - pozostałe są pod spodem, więc ich nie widać).
  • Obracamy podniesione karty o 180 stopni, w taki sposób, że po obróceniu górna karta znajduje się na dole, a dolna - na górze. Innymi słowy: odwracamy kolejność kart trzymanych w ręce.
  • Odkładamy karty na stos.
  • Proces powtarzamy tak długo, aż na górze stosu pojawi się jedynka.

Pytanie #1: Jaka jest maksymalna możliwa liczba kroków, po których trafimy na jedynkę?
Pytanie #2: Jakie musi być początkowe ułożenie kart, żeby tę maksymalną liczbę kroków uzyskać?

Czas - start!

https://xpil.eu/wjb

5 komentarzy

      1. Odpowiedź (wraz ze sposobem jej uzyskania) opublikuję w wtorek rano, więc masz jeszcze chwilę na zastanowienie.

  1. Metodą prób i błędów, wspomaganych skryptem prezentującym przebieg gry, wykombinowałem ciąg [9, 6, 12, 13, 7, 11, 4, 1, 3, 8, 2, 5, 10], który wymaga 71 ruchów, ale ogólnej zasady nie udało mi się znaleźć (poza stwierdzeniem, że mniejsze i większe liczby powinny być w miarę możliwości naprzemiennie, żeby się wzajemnie windowały z powrotem na początek, ale nie powinny to być liczby bezpośrednio sąsiadujące ze sobą), więc zapewne da się wycisnąć więcej.

    Powyższy ciąg po wykonaniu wszystkich ruchów daje w wyniku idealnie uporządkowany ciąg od 1 do 13, więc zgaduję, że maksimum można znaleźć idąc od końca i odpowiednio wybierając liczbę do obrócenia tak długo, aż żadna nie pozostanie na “swoim” miejscu – próbując tak robić, zatykałem się jednak dość szybko, więc nie jest to jeszcze prosta droga do rozwiązania.

    Można wprawdzie puścić brute force’a, przeliczenie tych ~6 mld kombinacji pewnie za wiele czasu by nie zajęło (zwłaszcza jeśli pominąć wszystkie z jakąkolwiek liczbą na “swoim” miejscu, bo każda taka kombinacja jest osiągalna z innej, więc nie może stanowić maksimum), ale to by było pójście na łatwiznę…

Skomentuj Butter Anuluj pisanie odpowiedzi

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.