死のパズルを解いて世界を救う方法

概要

この記事では、史前のウイルスが研究室で放出され、汚染されたすべての部屋で破壊する必要があり、世界を救うために死のパズルを探求します。このパズルは、解決が非常に困難なハミルトン路問題に関連しています。しかし、私たちはパズルのひねりを発見し、それを解決して、終末的な規模の流行を防ぐことができます。

死のパズル

永久凍土で発見され、研究のために分離された史前のウイルスがあるシナリオを想像してください。しかし、現時点ではウイルスは封じ込められていますが、破壊されない限り、換気口がすぐに開き、致死性のある空気感染症が放たれます。あなたの仕事は、世界を救うために汚染されたすべての部屋でウイルスを破壊することです。

研究室は、北西の隅に入り口があり、南東に出口がある16の部屋からなる4×4の複合体です。各部屋は、エアロックによって隣接する部屋に接続されており、ウイルスは入り口以外のすべての部屋で放出されています。ウイルスを破壊するには、汚染された各部屋に入り、緊急自己破壊スイッチを引く必要があります。しかし、注意が必要です。汚染された部屋に入ったら、スイッチをオンにしないと出ることができず、スイッチをオンにしたら、その部屋には戻れません。

ハミルトン路問題

あなたが最初に考えるのは、可能な移動をグリッド上にグラフ化することである場合、正しいアイデアを持っています。このパズルは、19世紀のアイルランドの数学者ウィリアム・ローワン・ハミルトンにちなんで名付けられたハミルトン路問題に関連しています。この問題の課題は、与えられたグラフにハミルトン路があるかどうかを見つけることです。それは、それぞれの点を1回だけ訪れるルートです。このタイプの問題は、NP完全と分類され、グラフが十分に大きい場合、非常に困難です。提案された解決策は簡単に検証できますが、1つを見つけるための信頼できる公式やショートカットはなく、また、それが可能かどうかすらわかりません。

パズルのひねり

このパズルは、特定のポイントで始めて終わらなければならないというハミルトン路問題にひねりを加えています。しかし、グラフ用紙を大量に無駄にする前に、真のハミルトン路はこれらのエンドポイントでは不可能であることを知っておく必要があります。それは、偶数の部屋がそれぞれの側にあるグリッドを形成しているためです。その構成を持つ任意のグリッドでは、対角線上のコーナーは同じ色になるため、対角線上のコーナーで始まり終わるハミルトン路は不可能です。

これがなぜかを理解するための1つの方法を以下に示します。偶数のマスが各側にあるチェッカーボードグリッドを考えてみましょう。それを通るすべての道は、黒と白が交互に現れます。これらのグリッドはすべて偶数の合計マスを持っているため、偶数の数×偶数の数は偶数になります。したがって、黒で始まるハミルトン路は白で終わり、白で始まるハミルトン路は黒で終わる必要があります。しかし、偶数の辺を持つグリッドでは、対角線上のコーナーは同じ色であるため、対角線上のコーナーで始まり終わるハミルトン路を開始することは不可能です。

パズルの解決方法

このように、あなたは運が悪いように思えますが、ルールを注意深く見て、重要な例外に気付くことができます。汚染された部屋でスイッチをオンにすると、部屋は破壊され、二度と戻ることはできません。しかし、入り口という汚染されていない部屋が1つあります。これは、スイッチを引かずに1回出ることができ、どちらかの部屋を破壊した後に戻ることができます。角の部屋はエアロックが開いたときに汚染されているかもしれませんが、2回目の訪問後に入り口を破壊することができるため、大丈夫です。この帰りの旅は、成功するルートの4つのオプションを提供し、この部屋を最初に破壊した場合にも同様のオプションを提供します。