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.
你的研究团队发现了一种 被保存在永冻土层的史前病毒, 你们将它分离出来用作研究。 在一整晚的工作后, 当你正关上实验室的门时, 一个突如其来的地震发生了, 导致电源断了。 启用紧急电源之后, 一声警报证实了你最惧怕的事: 所有的小药瓶样本已被打碎了。 病毒现在还存留着, 但是除非你能销毁它, 不久排风扇就会打开, 释放出这种通过空气传播的致命病毒。 毫不犹豫,你抓起了你的防护服 准备去拯救世界。 实验室是由4乘4, 16个房间组成的, 西北角有一个入口, 东南角一个出口。 每个房间都与相邻的房间由 气塞连接着, 除了入口那间, 病毒已经弥漫到了其他所有房间。 想要销毁它, 你必须进入每一个被污染的房间, 拉下各自的紧急自毁开关。 但是这里有个问题 因为安全系统是处于一级防范禁闭, 一旦你进入了被污染的房间, 你不开启开关就不能逃出去, 一旦你开了开关, 你就没法再回到那个房间去。 你开始在一叠纸上 画出可能的路线, 但是似乎找不到一个能够 不错过任何一个房间 就能走到出口的路线。 因此,要怎样才能销毁 每个被污染的房间 活着逃出来, 再给大家说起这段故事呢? 如果你想自己琢磨的话, 就按一下暂停键。 答案即将揭晓:3! 2! 1! 如果你的直觉是尝试在方格上 画出可能的路线的话, 你的想法是对的。 这个谜团与汉密尔顿路径有关, 它是以19世纪爱尔兰数学家 威廉·汉密尔顿命名的。 这个路径问题的挑战是 能否在已有图表上 找出一条汉密尔顿路径。 这是一条要求在每个点上 正好划过一次的路线。 这种类型的问题, 被归类为NP完全问题, 众所周知,当图表足够大时, 这问题奇难无比。 虽然任何提出的解决方法 都可以被轻易证实, 我们没有可靠的方程式或捷径 来找出这个方法, 或证明这个方法存在。 我们甚至也不确定能否依赖计算机 来可靠地找出这种解决方法。 这个难题又将汉密尔顿路径问题 提升了一个难度, 因为你要在一个特定的点开始, 并在另一个特定的点结束。 但是在浪费你无数的稿纸之前, 你应该知道真正的汉密尔顿路径 若用这些开始或结束的点, 是无法成立的。 那是因为房间形成一个表格, 每边房间的数量都是偶数。 在任何一个这样结构的表格里, 找出一条起点和终点在相反角落的 汉密尔顿路径是不可能的。 这有一个解释。 比如说一个棋盘两边 都有一个偶数量的正方格, 通过它的每条路径都会黑白交替。 这些方格的总数量将是偶数, 因为偶数与偶数的积是偶数。 因此在一个偶数边表格上, 汉密尔顿路径若是从黑色方格开始, 最终将在白色方格结束。 若是以白色方格开始的话, 就会以黑色方格结束。 但是,在任何偶数边表格中, 对角的颜色是相同的, 要找到一个起点和终点在对角的 汉密尔顿路径是不可能的。 似乎你已经没辙了, 但是如果你仔细看一下规则, 可以注意到一个很重要的例外。 没错,一旦你启动污染房间的开关, 它已自毁并且你再也没法回去了。 但有一个房间是没有被污染的, 就是入口的房间。 这意味着你可以在 不启动开关的情况下离开一次, 在你销毁与它相邻的两个房间 其中之一后,再回到入口房间。 角落的房间可能已经 因开着的气塞而被污染了, 但这没问题, 因为你可以在第二次进入之后 再销毁入口房间。 重返路线给你提供了 四条可行的路线, 如果你先销毁这个房间的话, 也会出现四类似的方案。 恭喜,你已经阻止了一个能导致 世界末日的传染病, 渡过这一难关之后, 你需要休息一下。 或许你应该答应那个工作机会, 去做一名旅行推销员。