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!
13, 11, 9, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12
widz臋 pewne niedok艂adno艣ci. Sprawdz臋 jeszcze 馃槈
Odpowied藕 (wraz ze sposobem jej uzyskania) opublikuj臋 w wtorek rano, wi臋c masz jeszcze chwil臋 na zastanowienie.
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臋…
71 to do艣膰 blisko maksimum, ale da si臋 wi臋cej.