ウォーリーの位置いちを明あかさずウォーリーを見みつけたことを証明しょうめいする「ゼロ知識ちしき証明しょうめい」を説明せつめいするための地図ちず塗ぬり分わけゲームが登場とうじょう

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に記しるしています。