ウォーリーの位置を明かさずウォーリーを見つけたことを証明する「ゼロ知識証明」を説明するための地図塗り分けゲームが登場

by Si1very

何かを証明したい人が「自分はある事柄を知っている」という事実を、他人に対して「知っている」という事実以外の知識を与えることなく証明する技術が「ゼロ知識証明」です。ゼロ知識証明の例えとして挙げられるのがウォーリーをさがせ！で、具体的には「ウォーリーを見つけた際に、ウォーリーの場所を明かさずに見つけたことだけを証明する」というもの。そんなゼロ知識証明をはじめとする、さまざまな数学上の問題や定理などを直感的に理解できるゲームが公開されています。

rahulilango.com/coloring/
https://www.rahulilango.com/coloring/

上記URLにアクセスすると、紫色で塗られたイギリスおよびアイルランドの地図が表示されます。この地図を、「隣接する2つの地域が同じ色にならないように色分けしてください」というのが最初の問題です。

地図をクリックして色分けに成功すると、「この地図では2色で色分けができます」と表示されました。問題をクリアすると画面下部に「Next Challenge！」というボタンが出現するのでこれをクリック。

次の問題が以下。問題は「物理的に隣接する2つのエリアが同じ色にならないように色分けしてください」というもの。

これも先ほどの問題と大きな差はない簡単な問題です。「Next Challenge！」をクリック。

次の問題は「物理的に隣接するエリアが同じ色にならないように色分けするには3つの色が必要となるような地図を作成できますか？」というもの。画面下部の赤枠部分にマウスポインタ―を動かして線を引き、地図を作成します。

地図の作成に成功したら「Next Challenge！」をクリック。

次の問題は「南アメリカ北部の地図を物理的に隣接するエリアが同じ色にならないように色分けしてください」というもの。

以下の地図の色分けに必要な色の最小数は「3」でした。「Next Challenge！」をクリック。

次の問題は「物理的に隣接するエリアが同じ色にならないように色分けするには4つの色が必要となるような地図を作成できますか？」というもの。どうしても適切な形が思い浮かばないという場合は、「Hint」をクリックすればヒントが得られます。

なんとか地図の作成にクリアしたら「Next Challenge！」をクリック。ヒントを複数回クリックすれば回答が表示されるので、どうしても回答が思い浮かばないという人でも次の問題に進むことができます。

その後、実際の地図を使って複数の問題が出題されます。

「アメリカ西部の地図を物理的に隣接するエリアが同じ色にならないように色分けしてください」

「南アメリカの地図を物理的に隣接するエリアが同じ色にならないように色分けしてください」

これらの問題に正解すると、「物理的に隣接するエリアが同じ色にならないように色分けするには5つの色が必要となるような地図を作成できますか？」という問題が出題されました。画面下部にあるように非常に難しい問題であるため、「色々挑戦した後にスキップしてください」と、あらかじめ「Skip」ボタンまで用意されています。

問題をスキップすると、「あらゆる地図を塗り分けるには4色あれば十分か否かについて、世界有数の数学者は頭を悩ませてきました。この疑問が最初に浮上したのは100年以上も前のことです」と表示され、「4 is enough！(4色あれば十分！)」「4 is not enough!(4色じゃ不十分！)」というボタンが表示されます。

これは「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分である」という四色定理を体感するためのゲームだったわけです。四色定理については1976年にコンピューターを用いてあらゆる可能性を検証し、「塗り分けには4色あれば十分」であることが証明されています。しかし、これを証明するにはコンピューターなしだとあまりに複雑すぎるそうです。

さらに深い謎があるとのことで、画面下部の緑色のボタンをクリック。

次の問題は、以下のような複雑な地図があったとして、「この地図を隣接するエリアが異なる色になるよう塗り分けるには何色必要ですか？」という問いに素早く回答できるか否かを問うもの。「私は3色で十分だと主張しますが、信じてもらえますか？」と書かれており、イエスなら上のボタン、ノーなら下のボタンをクリックすればOK。

3色で塗り分けられることを証明する最も簡単かつ明瞭な方法は、パズルを3色で塗り分けることです。しかし、そうしてしまうとパズルを解くという体験が台無しになってしまいます。そこで「答えを明かさずに相手を説得することはできるでしょうか？」というのが今回の問い。不可能なら左、可能なら右のボタンをクリック。

答えはイエスで、回答を提示することなく「塗り分けには3色で十分」であることを示すことが可能です。

簡単な例が以下の通り。

ステップ1：
各領域に紫・青・赤といった具合に色を配置し、これをポストイットで隠します。なお、ポストイットを貼った後は色を変更することができないと仮定します。

ステップ2：
任意の2つのポストイットをはがし、異なる色が配置されていることを確認します。

ステップ3：
ステップ1とステップ2を、相手が満足するまで繰り返します。ただし、色を確認する際は毎回ポストイットの下の色を入れ替えます。

これがゼロ知識証明と呼ばれるものです。相手に見せるのはマップの色分けの一部のみであるため、相手には正確な色分け方法(回答)はわかりません。また、相手が満足するまで何度も回答(色分け)を変更してみせるわけですが、回答は毎回変更されるため見た色をつなぎ合わせて回答を導き出すことも不可能です。加えて、何度も回答を変えてみせることで、自身が回答を理解していることを相手に示すことができます。

なお、ゲームの作者はマサチューセッツ工科大学コンピューターサイエンス課程の博士学生であるRahul Ilango氏です。同氏は「私の好きな数学の問題やアイデアのいくつかをインタラクティブに説明するためにこのゲームを作成しました。私の目標は主にプレイヤーの好奇心を刺激することにあり、必ずしもすべてを説明することではありません」とHacker Newsに記しています。