Hádanka se smrtícím viremTED-Ed

Váš výzkumný tým našel prehistorický virus, který byl uchován v permafrostu, a izoloval ho pro následné zkoumání. Po dlouhé noci v práci zrovna zavíráte laboratoř, když najednou udeří zemětřesení a způsobí výpadek elektřiny. Když naběhnou záložní generátory, alarm potvrdí vaše nejhorší obavy. Všechno zkumavky s virem se rozbily. Virus je zatím izolován, ale pokud ho nezničíte, zanedlouho se spustí klimatizace, která tento smrtící virus vypustí do světa.

Bez váhání popadnete ochranný oblek a připravíte se zachránit svět. Laboratoř je tvořena 16 místnostmi, v mřížce 4 krát 4 místnosti. Vstup do ní je na severozápadním rohu a východ je v jihovýchodním. Každá místnost je spojena s vedlejšími pomocí přetlakové komory a virus byl vypuštěn ve všech místnostech, s výjimkou vstupu. Abyste ho zničili, musíte vstoupit do každé kontaminované místnosti a zatáhnout za páku autodestrukce.

Ale má to háček. Protože je aktivní karanténa, jakmile vstoupíte do kontaminované místnosti, nemůžete odejít, aniž byste za páku zatáhli. A jakmile to uděláte, nebudete se do této místnosti moci vrátit. Začnete si na papír kreslit možné cesty, ale zdá se, že se nemůžete dostat k východu, aniž byste nevynechali aspoň jednu místnost.

Jak tedy můžete zničit virus v každé kontaminované místnosti a přežít toto dobrodružství? POKUD CHCETE NA ŘEŠENÍ PŘIJÍT SAMI, VIDEO SI NYNÍ ZASTAVTE PRAVIDLA JSOU V POPISKU ODPOVĚĎ ZA: 3, 2, 1. Pokud je vaším prvním instinktem udělat si graf možných cest, jdete na to správně.

Tato hádanka souvisí s problémem hamiltonovské cesty. Ta je pojmenována po irském matematikovi z 19. století, Williamu Rowan Hamiltonovi. Problémem hamiltonovské cesty je zjistit, má-li daný graf tzv. hamiltonovskou cestu. To je cesta, která navštíví každý bod tohoto grafu právě jednou. Tento typ problému, který je klasifikován jako NP-úplný, je nesmírně obtížný, je-li graf dostatečně veliký. Přestože lze jakékoliv navrhované řešení jednoduše ověřit, nemáme žádný spolehlivý vzorec či zkratku, jak k němu dojít.

Nebo jak zjistit, zda vůbec existuje. A nejsme si ani jisti, jestli je možné, aby počítač spolehlivě takové řešení našel. Tato hádanka přidává do problému hamiltonovské cesty další podmínku, protože musíte začít a skončit na konkrétních místech. Ale než vyplácáte tunu papíru, měli byste vědět, že hamiltonovská cesta není s těmito body možná.

To proto, že místnosti tvoří mřížku se sudým počtem místností na obou stranách. V každé mřížce, která je takto nastavena, je nemožné vytvořit hamiltonovskou cestu, jejíž začátek a konec jsou v protilehlých rozích. Zde je příklad, který to může osvětlit. Představte si šachovnici, která má na každé straně sudý počet polí. Na každé cestě se budou střídat černá a bílá pole. Tyto mřížky budou také mít sudý celkový počet polí, protože sudé číslo krát sudé číslo dává sudý výsledek.

Takže hamiltonovská cesta na mřížce o sudém počtu polí, která začíná na černém poli, bude muset skončit na bílém poli. A ta, která začíná na bílém poli, musí skončit na černém. Avšak v každé mřížce o sudé velikosti stran mají protilehlé body stejnou barvu, takže je nemožné začít a skončit hamiltonovskou cestu v protilehlých rozích. Zdá se, že máte smůlu, pokud se pořádně nepodíváte na pravidla a nevšimnete si důležité výjimky.

Je pravda, že jakmile aktivujete páku v kontaminované místnosti, je místnost zničena a vy se nemůžete vrátit. Ale jedna místnost kontaminována nebyla. Vstup. To znamená, že z ní můžete jednou odejít, aniž byste za páku zatáhli, a vrátit se do ní poté, co jste zničili jednu z těchto dvou místností.

Je možné, že byla tato místnost tímto krokem kontaminována. Ale to nevadí, protože vstup můžete nyní zničit. Tato zpáteční cesta vám dává čtyři možnosti cesty, a podobné možnosti, pokud jste nejprve zničili tuto místnost. Gratulujeme, zabránili jste epidemii apokalyptických rozměrů. Ale po tak náročné akci potřebujete pauzu. Možná byste měli přijmout pracovní nabídku a stát se obchodním cestujícím.

Překlad: Xardass www.videacesky.cz