Wasz zespół badawczy znalazł prehistorycznego wirusa
zakonserwowanego w wiecznej zmarzlinie
i wyizolował go do badań.
Późno zamykasz laboratorium,
gdy nagle uderza trzęsienie ziemi
i siada zasilanie.
Gdy włączają się generatory awaryjne, alarm potwierdza twoje najgorsze obawy:
wszystkie fiolki z próbkami pękły.
Wirus jest na razie pod kontrolą,
ale jeśli go nie zniszczysz,
wkrótce otworzą się otwory wentylacyjne i wirus wydostanie się na zewnątrz.
Bez wahania chwytasz kombinezon HAZMAT,
przygotowując się do ocalenia świata.
Laboratorium składa się z 16 sal
o wymiarach cztery na cztery z wejściem w północno-zachodnim rogu
i wyjściem na południowym wschodzie.
Każdy pokój jest połączony z sąsiednim śluzą powietrzną,
a wirus jest w każdym pokoju z wyjątkiem wejścia.
Aby go zniszczyć, musisz wejść do każdego pomieszczenia
i pociągnąć za awaryjny włącznik samozniszczenia.
Ale jest haczyk.
Ponieważ system bezpieczeństwa został uruchomiony,
po wejściu do skażonego pomieszczenia
nie można wyjść bez aktywacji włącznika,
a po jego uruchomieniu
nie będzie można wrócić do tego pomieszczenia.
Zaczynasz rysować możliwe trasy na kartce papieru,
ale żadna droga nie prowadzi do wyjścia
bez pominięcia przynajmniej jednego pokoju.
Jak zniszczyć wirusa w każdej skażonej sali
i przeżyć, żeby opowiedzieć tę historię?
Wstrzymaj nagranie, żeby znaleźć sposób.
[Odpowiedź za: 3]
[Odpowiedź za: 2]
[Odpowiedź za: 1]
Jeśli w pierwszym odruchu
rysujesz opcje tras na siatce,
idziesz w dobrym kierunku.
Ta zagadka wiąże się z problemem cyklu Hamiltona,
nazwanym na cześć irlandzkiego matematyka z XIX wieku - Williama Rowana Hamiltona.
Trudność w problemach z trasą polega na ustaleniu,
czy dany graf ma cykl Hamiltona,
czyli czy można przejść przez każdy punkt dokładnie raz.
Klasyfikuje się to jako problem NP-zupełny
i jest notorycznie trudny, gdy liczba punktów jest duża.
Choć każde zaproponowane rozwiązanie można łatwo zweryfikować,
nie ma niezawodnej formuły ani skrótu, aby je znaleźć
lub określić, że istnieje.
Nie mamy nawet pewności, czy komputery umieją
niezawodnie znaleźć takie rozwiązanie.
Ta łamigłówka dodatkowo utrudnia cykl Hamiltona,
bo musi zaczynać się i kończyć w określonych punktach.
Ale zanim zmarnujesz mnóstwo papieru,
musisz wiedzieć, że prawdziwa ścieżka Hamiltona
nie jest możliwa z naszymi punktami końcowymi.
Dzieje się tak, bo pokoje tworzą siatkę
z parzystą liczbą pokoi po każdej stronie.
W każdej siatce z taką konfiguracją
ścieżka hamiltonowska,
która zaczyna się i kończy w przeciwległych narożnikach,
jest niemożliwa.
Oto przykład, dlaczego.
Rozważmy siatkę szachownicy
z parzystą liczbą kwadratów po każdej stronie.
Każda ścieżka idąca przez nią będzie na przemian czarno-biała.
Wszystkie te siatki będą miały też parzystą całkowitą liczbę kwadratów,
bo wynik mnożenia liczb parzystych jest parzysty.
Ścieżka hamiltonowska na parzystej siatce,
która zaczyna się na czarnym polu,
musi się kończyć na białym,
a zaczynając na białym, kończymy na czarnym.
Jednak w każdej siatce z parzystą liczbą boków
przeciwległe rogi są tego samego koloru,
więc nie da się zacząć i zakończyć ścieżki Hamiltona
na przeciwnych rogach.
Wygląda na to, że nie masz szczęścia,
chyba że dokładnie przyjrzysz się zasadom i zauważysz ważny wyjątek.
To prawda, że po aktywacji przełącznika
skażone pomieszczenie jest zniszczone, i nigdy nie można tam wrócić.
Ale jest jedno pomieszczenie, które nie było skażone - wejście.
Oznacza to, że można je raz opuścić bez konieczności pociągania za włącznik
i wrócić tam po zniszczeniu któregoś z tych dwóch pomieszczeń.
Pokój narożny mógł zostać skażony
po otwarciu śluzy powietrznej, ale to nie szkodzi,
bo można go zniszczyć po drugiej wizycie.
Taki pomysł na przejście daje cztery opcje na udaną trasę
i podobny zestaw opcji, jeśli najpierw niszczysz tę salę.
Gratulacje, zapobiegasz epidemii o apokaliptycznym rozmiarze,
ale po tak stresującym wydarzeniu potrzebujesz przerwy.
Może warto wziąć inną ofertę pracy i zostać komiwojażerem.