Czy rozwiążesz zagadkę z wirusem? - Lisa Winer

Zobacz całą lekcję: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Wasz zespół badawczy znalazł w wiecznej zmarzlinie zakonserwowanego prehistorycznego wirusa i wyizolował go do badań. Późno zamykasz laboratorium, gdy nagle uderza trzęsienie ziemi i siada zasilanie. Czy zdołasz zniszczyć wirusa zanim otworzą się otwory wentylacyjne i wypuszczą go na zewnątrz? Lisa Winer pokazuje, jak to zrobić.

Lekcja: Lisa Winer, animacja: Artrake Studio.

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.