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.
你的研究團隊 在永凍層發現了史前病毒 並將它隔離研究 深夜,在結束工作後 你關上實驗室,一場突然的地震 震斷了電源系統 隨即,緊急電源啟動了 但警報聲通知你最害怕的事情: 所有的試樣瓶已經碎裂 病毒仍在實驗室裡 但是,除非你能摧毀它 通風口很快就會打開 在空氣中釋放致命的瘟疫 你沒有猶豫,穿起了化學防護衣 準備拯救世界 實驗室由四乘四,共十六間房間組成 入口在西北角,出口則在東南角 每個房間都有氣閘通往另一個房間 除了入口那間,病毒已經擴散至 其他所有的房間 要摧毀它 你得進入每個被汙染的房間 拉下緊急自毀開關 但是,有一個問題 因為保安系統是上鎖的 一旦你進入被汙染的房間 除非啟動開關,否則你無法離開 而且一旦啟動 你就無法再回到那個房間 你開始在一沓紙張上繪製可能的路線 但似乎沒有辦法走到出口 且不遺漏任何房間 所以,你要如何摧毀所有的病毒 並活下來講述這個故事呢? 如果你想自己找出答案 請先暫停一下 3 2 1 如果你的第一反應是 繪製所有可能的路線 你的想法是正確的 這個謎題關係到「哈密頓路徑問題」 以 19 世紀愛爾蘭數學家 哈密頓之名來命名 路徑問題的挑戰是找出 一張特定的圖是否具有哈密頓路徑 這條路線會經過所有的節點 且只經過一次 這類型的問題,被歸類在 「非決定性多項式完全」(NP-complete) 當圖夠大時,它會變得非常困難 雖然,任何提出的路線 都可以被輕易地驗證 我們卻沒有可靠的公式或捷徑 來找出正確的那條 或確定它存在 我們甚至不知道 電腦是否能可靠地找出解決方案 這道謎題在哈米頓路徑問題上 增加了變化 你必須由特定的起點前往特定的終點 但在你浪費大量的方格紙前 你要知道,真正的哈密頓路徑 是不可能連接這些端點的 因為房間所形成的網格 每邊都為偶數個房間 任何這種配置的網格 哈密頓路徑是不可能 從相對的角落開始並結束 原因如下 想像一個正方的棋盤,每邊有偶數格 任一條路徑皆交替地經過黑格及白格 這些正方網格,總共也是偶數個 因為偶數乘偶數仍為偶數 所以,哈密頓路徑在偶數邊的網格 會從黑格開始,並結束在白格 而從白格開始,則會在黑格結束 然而,在任何偶數邊的網格中 相對的角都是相同的顏色 所以哈密頓路徑不可能 在相對的角落開始並結束 看似是你不走運了 除非,你有仔細看過規則 且注意到一個例外 一旦你在受汙染的房間啟動開關 病毒會被摧毀,且你不可能回去 但是,有一間未受汙染的房間 入口的那一間 這意味你不需要拉開關就能離開房間 並在摧毀相鄰的其中一間後回來 角落的房間可能會 在你開啟氣閘時受到汙染 但沒有關係 因為你可以在第二次進入時 摧毀入口的那一間 這個返程能提供你四條成功路線 如果你先摧毀這間 也會有四條成功路線 恭喜,你阻止末日瘟疫了 在這緊張的事件後,你需要休息一會 也許你該接受最近那份 旅行推銷員的工作邀約了