Zapętlony pociąg: rozwiązanie zagadki

https://xpil.eu/1h7 📋

Aby policzyć wagony w zapętlonym pociągu, trzeba znaleźć jakiś sposób na oznakowanie wagonu. Skoro jednak znakować moczem ani nożykiem nie wolno, będziemy "znakować" za pomocą żarówki. Na przykład: żarówka włączona - brak znaku. Żarówka wyłączona - znak!

Skąd jednak wiedzieć, czy wyłączona żarówka jest efektem początkowego ustawienia zagadki czy naszego własnoręcznego jej wyłączenia?

Jedynym sposobem, aby mieć pewność, że to my wyłączyliśmy żarówkę, jest przejście tych samych wagonów dwukrotnie:

• Najpierw ustalamy jakąś liczbę N, odpowiednio dużą, żeby mieć nadzieję, że jest nie mniejsza od liczby wszystkich wagonów, ale nie za dużą, żeby się nie zmachać za bardzo. Optymistycznie możemy przyjąć N=2 w płonnej nadziei, że są tylko dwa wagony.
• Potem przypisujemy wagonowi, w którym jesteśmy numer 0
• Następnie zaczynamy wędrówkę (w lewo lub w prawo, wsioryba, byleby ciągle w tą samą stronę), numerując kolejne wagony narastająco i włączając w nich żarówki.
• Po dojściu do wagonu numer N wyłączamy w nim żarówkę, resetujemy licznik i zawracamy. Innymi słowy wagon z wyłączoną żarówką (ten ostatni) ma teraz numer zero, kolejny - jeden i tak dalej.

Prędzej lub później wydarzy się jedna z dwóch rzeczy:

albo

• Dojdziemy do wagonu numer N (przypominam, jesteśmy w drodze powrotnej, a więc idziemy przez wagony, przez które już szliśmy) nie napotkawszy na wyłączoną żarówkę. Oznacza to, że niestety przyjęliśmy zbyt małe N (wszystkich wagonów jest więcej niż N) i musimy zacząć od nowa z większym N

lub

• Dojdziemy do wagonu z wyłączoną żarówką zanim skończą nam się numery w drodze powrotnej - oznacza to, że liczba, do której doliczyliśmy wracając jest zarazem liczbą wszystkich wagonów - zagadka rozwiązana.

Jeżeli się nie udało (innymi słowy, jeżeli nie natrafiliśmy na wyłączoną żarówkę w drodze powrotnej), musimy przyjąć większe N i zacząć od nowa.

Czy powyższa metoda gwarantuje nam rozwiązanie zagadki?

Tak! Oczywiście pomijamy tak urocze zagadnienia jak śmierć z odwodnienia, bo pociąg ma kilkadziesiąt albo kilkaset tysięcy wagonów i padniemy przed zakończeniem zagadki, albo że złamiemy sobie nogę przechodząc między wagonami, albo że dopadnie nas atak paniki i schowamy się pod jednym z siedzeń czekając na lepsze czasy... Jednak logicznie przecz biorąc metoda jest poprawna.

Tylko że to nie wystarczy. W treści zagadki widnieje przecież wyraźnie, że trzeba znaleźć metodę gwarantującą policzenie wagonów w możliwie najmniejszej liczbie kroków.

Innymi słowy trzeba jeszcze wykombinować jak najlepiej dobierać kolejne N, żeby całość zajęła jak najmniej kroków.

Pierwsze co przychodzi do głowy, to ustalanie w kolejnych podejściach N o jeden większe niż poprzednio. Wówczas:

Jeżeli, dajmy na to, pociąg ma dziesięć wagonów, a wystartujemy od N = 2, to:
- w pierwszym cyklu robimy 4 kroki, w drugim 6, w trzecim 8, i tak dalej aż do dziesiątego cyklu, w którym zrobimy 20 kroków (koniec). Tym samym razem zrobimy łącznie 108 kroków.

Przy dwudziestu wagonach będzie to już 418 kroków, a przy trzydziestu - 928. Jak widać liczba kroków rośnie proporcjonalnie do kwadratu liczby wagonów, a to kiepski znak. Można lepiej.

Okazuje się, że lepiej jest podwajać N z każdą iteracją. A więc zaczynamy od 2, potem 4, 8, 16, 32 i tak dalej, aż natrafimy na N wystarczająco duże do udzielenia odpowiedzi.

Oczywiście zawsze możemy natrafić na kiepski wariant, w którym wagonów będzie o jeden więcej niż całkowita potęga dwójki i wtedy w ostatniej iteracji "zmarnujemy" prawie połowę kroków na bezdurno, ale w ogólnym rozrachunku i tak bardziej opłaca się to podejście od inkrementalnego. Głównie dlatego, że liczba kroków rośnie tu liniowo z liczbą wagonów (i wynosi w najlepszym przypadku 4N-2 a w najgorszym: 7N-8)

Istnieje jednak odrobinę lepsza metoda wymagająca w najlepszym przypadku zaledwie 3N-1 kroków, a w najgorszym - 5N-5.

Jej odszukanie pozostawię już Czytelnikowi.

https://xpil.eu/1h7 📋