Zagadka o zapętlonym pociągu

https://xpil.eu/ojg

Dziś znów zagadka. Tym razem jednak o wiele ciekawsza niż ostatnio i na pewno z prawidłowym rozwiązaniem, które podam za kilka dni, o ile rzecz jasna któryś z Czytelników nie poda wcześniej poprawnej odpowiedzi w komentarzu.

A więc tak: jesteśmy w pociągu. Ale nie w jakimś tam sobie byle jakim pociągu, tylko w takim specjalnym: zapętlonym. Coś jakby wąż pożerający własny ogon, pociąg ma same wagony (bez lokomotywy), które są ustawione w kółko i połączone jeden z drugim.

Pociąg nie ma okien.

W każdym wagonie jest dokładnie jedna żarówka oraz pstryczek, za pomocą którego możemy tę żarówkę włączyć lub wyłączyć. Albo zapalić lub zgasić, jak zwał tak zwał.

Możemy:

  • Przechodzić między wagonami oraz
  • Przełączać żarówki w każdym wagonie

Nie możemy:

  • Zajrzeć do sąsiedniego wagonu, żeby sprawdzić czy żarówka się tam świeci czy nie (między wagonami są automatyczne drzwi)
  • Wyjść ani nawet wyjrzeć z pociągu na zewnątrz
  • Oznaczać wagonów w żaden sposób z wyjątkiem włączania lub wyłączania żarówek.

Nie wiemy ile jest wszystkich wagonów.

Wiemy natomiast, że żarówki we wszystkich wagonach są na dzień dobry powłączane losowo - w jednych się świecą, w innych nie.

No i teraz pytanie: jak w najmniejszej liczbie kroków (rozumianych jako przejścia z wagonu do wagonu) ustalić ponad wszelką wątpliwość ile jest wszystkich wagonów w tym pociągu?

P.S. W treści zagadki nie ma ani słowa o minimalnej liczbie wagonów - załóżmy więc, że dolnym ograniczeniem jest 2. Nie ma to za bardzo sensu z technicznego punktu widzenia, ale z drugiej strony pociąg stojący w kółko na okrągłym torze też nie ma, więc się wyrównuje.

https://xpil.eu/ojg

8 komentarzy

  1. Trzeba oznaczyć któryś wagon i mierzyć ilość wagonów względem niego. Proponuję algorytm w stylu: zapamiętujemy stan światła w pierwszym wagonie (startowym) i idziemy powiedzmy w prawo, ustawiając stan światła tak, by był odwrotny niż w wagonie startowym i licząc wagony. Za każdym razem, gdy w nowym wagonie napotkamy przy wejściu stan jak w startowym, zmieniamy go i wracamy do startowego sprawdzić, czy przypadkiem się nie zmienił. Jeśli się zmienił – właśnie poznaliśmy ilość wagonów. Jeśli nie – wracamy do wagonu, gdzie dokonaliśmy zmianę i kontynuujemy podróż.

    1. Algorytm można usprawnić: jak zgasisz światło w N-tym wagonie (dla wygody zakładam, że w początkowym [numer zero] jest włączone) i po powrocie do startowego stwierdzisz, że dalej się pali, to idziesz w drugą stronę (gasząc ewentualne światła) tak długo, aż znajdziesz ciąg przynajmniej N zgaszonych i dopiero wtedy szukasz kolejnego z zapalonym światłem i po jego zgaszeniu wracasz na początek – dzięki temu w każdym kolejnym cyklu zajdziesz znacznie dalej niż w poprzednim.

      1. No właśnie kombinuję i na razie wymyśliłem, że w jedną stronę od startowego ustawiamy wszystkie światła w stan zapalony, w drugą – zgaszony i zliczamy ilości wagonów o znanym stanie w obie strony niezależnie. Przy każdej zmianie stanu idziemy do najdalszego znanego wagonu o stanie z którego zmienialiśmy i po sprawdzeniu kontynuujemy z niego w kierunku gdzie jest wagon o nieznanym stanie.

        To Twoje nie zapętli się w skrajnym przypadku? Ciąg “przynajmniej N zgaszonych” może się nigdy nie skończyć. 😉

        1. Jeśli wagon startowy jest zapalony – a z założenia jest, jeśli nie jesteśmy w fazie powrotnej – to zapętlenie nam nie grozi. A ustawiania różnych stanów po obu stronach trochę nie rozumiem – co to nam daje, skoro i tak po dojściu do wagonu w innym stanie trzeba wrócić na początek?

          1. Z założenia wagon startowy jest zapalony lub nie. Co do reszty się nie wypowiadam, żeby za dużo nie podpowiedzieć i dać szansę innym.

  2. Wykombinowałem lepszy algorytm: zapalamy światło w wagonie zero i idziemy w poszukiwaniu drugiego z zapalonym światłem; jak go znajdziemy na pozycji N, to idziemy dalej w poszukiwaniu ciągu dokładnie N – 1 ciemnych wagonów, z jasnymi wagonami przed i po, gasząc wszystko po drodze. Jak już takowy znajdziemy, to znajdujemy się w kończącym ciąg jasnym wagonie na pozycji M, który być może jest tym samym co N, więc gasimy i wracamy sprawdzić. Jeśli N dalej się świeci, to wracamy na start i idziemy w drugą stronę szukając ciągu co najmniej M – N ciemnych, po którym nastąpi jeden jasny, N – 1 ciemnych i znowu jeden jasny… I tak dalej. Nawet jeśli nie będzie to optymalne, to przynajmniej bardzo wydajne – choć też i pamięciożerne, jeśli nie mamy przy sobie czegoś do pisania.

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.