Name: 【TED-ED】你能解開病毒之謎嗎？- 麗莎-溫納 (【TED-Ed】Can you solve the virus riddle? - Lisa Winer)
Uploaded: 2021-01-14T06:49:07.000Z
Duration: 5 min 13 s

Your research team has found a prehistoric virus preserved in the permafrost

你們的研究團體在永久凍結帶發現了一個史前病毒

you're just closing up the lab when a sudden earthquake hits

你們才將關起實驗室時，一個突如其來的地震發生了

As the emergency generators kick in, an alarm confirms your worst fears:

當發電機開始運轉發電時，一個警報器證明我們最擔心的事終究發生了

the vents will soon open and unleash a deadly airborne plague.

再過不久，排氣孔也將打開，空氣中則將散發著致命的病毒

Without hesitation, you grab your HazMat suit

你們話不多說的馬上套上防護裝

The lab is a four by four compound of 16 rooms

實驗室是4×4的大小，總共有16間

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.

Because the security system is on lockdown,

所以，一旦你進入一個汙染的空間

you can't exit without activating the switch,

除非你們能啟動裝置，否則你們是無法逃出

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

那你們要怎麼消滅每個房間中的病毒

而之後能與眾人分享這個故事呢？

Pause here if you want to figure it out for yourself.

你們可以按下暫停，來思考一下要怎麼解決這個問題

If your first instinct is to try to graph your possible moves on a grid,

如果你們第一個想法是先在紙上畫路線圖

This puzzle is related to the Hamiltonian path problem

這個難題與哈密頓路徑問題相關

named after the 19th century Irish mathematician William Rowan Hamilton.

在１９世紀，由愛爾蘭數學學家威廉．盧雲．哈密頓所命名的

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,

但，我們沒有一個準確或捷徑方式來找到一個完美路徑

And we're not even sure if it's possible for computers

我們甚至也無法確定電腦系統們

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

你們都應該知道一個真正的哈密頓路徑

That's because the rooms form a grid with an even number of rooms on each side.

這是因為這每一個房間都是由偶數方格構成的

a Hamiltonian path that starts and ends in opposite corners is impossible.

一條哈密頓路徑開始的蛇行路徑結束於相對角的點，結果會是少經過一個點

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

所以，一條哈密頓路徑從一個黑色四方格開始

And one that starts on white will have to end on black.

而如果從白色四方格開始，則會結束於黑色四方格

However, in any grid with even numbered sides,

但是，在任何一個偶數邊的四方格中

so it's impossible to start and end a Hamiltonian path on opposite corners.

所以，這樣下來是不可能可以開始以及結束於不同的地方

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.

或許你們應該考慮，去當個旅遊業務員