Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.
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.