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.
あなたの研究チームは 有史以前のウィルスが 永久凍土の中に 保存されているのを発見し 研究のために取り出しました 夜遅くまで作業をした後 研究所の戸締りをしようとしたその時 突然地震が起こり 停電しました 非常電源装置が立ち上がり 警告音で最悪の事態が起きたとわかります サンプルの入った瓶が 全て割れました ウィルスは今のところ 部屋の中に留まっていますが 死滅させない限り 通風口は間もなく開き 空気感染する伝染病が放たれてしまいます あなたはためらうことなく 防護服をつかむと 世界を守る体制に入りました 研究所には4x4の16部屋あり 入口は北西の角に 出口は南東の角にあります 各部屋は隣室と エアロックでつながっていて ウィルスは入口以外の全室に 広がっています 死滅させるためには 汚染された各部屋に入り 非常用自己破壊のレバーを 引かなければなりません しかし落とし穴があります ひとたび汚染された部屋に入ると 防犯システムが作動し 封鎖するので 作動用レバーを引かないと 出ることができず ひとたび作動させると その部屋に戻ることはできなくなります あなたは可能なルートを 紙に書き出してみますが 出口にたどりつくには 通らない部屋が少なくとも1つは 残されてしまうようです どうやったら全ての汚染された部屋の ウィルスを死滅させた上で 生還して 事件を報告できるでしょうか ご自身で考えたい方は ここで止めてください 解答まで 3 2 1 最初に格子に可能な動きを グラフで描くことを思いつけば 正しい方向で考えています このパズルは 19世紀のアイルランドの数学者 ウィリアム・ローワン・ハミルトンにちなんだ ハミルトン閉路問題に関係があるのです 閉路問題の課題は 与えられたグラフにハミルトン閉路が あるかどうかを定めることです これは 全てのポイントを きっちり1回訪れるルートのことです NP完全問題に分類されるこの手の問題は グラフが十分に大きくなると 難しくなることで悪名高いものです 解として提案された経路が正しいかどうかを 確めることは容易にできますが 解を探索するための 信頼のおける方法や簡便法などなく ルートがあるかどうか 決定できる方法もありません さらにコンピュータなら 安定的に解を探し出せるのか それすら はっきりと分かっていません このパズルは始点と終点が それぞれ特定されているという点で ハミルトン閉路問題に ひねりが加えられています しかし大量のグラフ用紙を 無駄にする前に 真のハミルトン閉路問題なら このような始点と終点では 正解がないことを 理解しなければなりません 部屋の数が縦も横も 偶数になっているからです このような配置をもった いかなる格子においても 始点と終点が対角にあるハミルトン閉路には 解答がありません なぜかを理解する方法を ひとつ紹介します 各辺が偶数であるチェッカー盤で 考えてみましょう 1部屋通過するごとに 黒と白が入れ替わります この格子はマスの合計も 偶数になっています 偶数同士の掛け算の積は 偶数になるからです だから黒で始まる偶数辺の ハミルトン閉路は 白で終わります 一方 白で始まれば 黒で終わります しかし各辺が偶数の格子では 対角にある角同士は同じ色になります つまりハミルトン閉路で一方の角から始めて 反対側の角で終わることは不可能です あなたの運は尽きてしまったようです でも注意深くルールを読み ある重大な例外に気付けばそうではありません 汚染された部屋のスイッチを 一度作動させると 部屋は破壊され二度と戻れない という事実があります しかし汚染されていない部屋が1つあります そう入口です つまりレバーを引かずに 入口の部屋を出て 両隣のどちらかの部屋を破壊した後に 戻ることができるのです 角部屋はエアロックの 開いたところから 汚染されているかもしれません それでも大丈夫 入口の部屋は2度目に入ったときに 破壊すればよいのです そこから出口に向かい 成功する経路は4通りあります こちらの部屋を最初に破壊しても 同様の選択肢が得られます おめでとう 世紀末的な 大流行を防ぐことができました しかしこんなストレスの掛かる仕事は うんざりですね 最近 求人募集のあった 「巡回セールスマン」なんかどうですか?