この記事はImpossible Escape?というページに登場する論理クイズ「2人の囚人とチェス盤」解説文を極めてテキトーに意訳してまとめたものです。
誤訳が訳出漏れがあっても寛大な心で見なかったことにしてください。
本文中で「脚注」とあるものは訳出者が付記したものです。
また、「クリックしてください」「左の図をご覧ください」といった文章はすべて原文に準拠したものす。それらに該当する図やインタラクティブな動的要素などは当記事には存在しません。その場合は原文ページをご参照ください。
原文ページを見ながら当記事を活用していただければ、より一層の理解が進むものと思われます。
また、この原文で述べられている「2人の囚人とチェス盤」を元にしたと思われる論理クイズ「2人の少女とチェス盤の部屋」について詳しく解説しました。
あわせてご参照ください。
超難問論理クイズ「2人の幼女とチェス盤の部屋」が本当に難しすぎた
目次
脱出不可能？
ある日、私はとても面白いパズルを耳にしました。
有名なprisoner problem（囚人問題）のひとつで、知性を見せつけて問題に正解しねーと心がねじ曲がった看守に殺されてしまう類のアレです。
あなたと友人は投獄されています。
看守はある難問を突きつけてきました。それを突破すれば2人とも牢獄から脱出して自由の身です。
以下がルールです。
・看守とあなたは個室に入る。個室には8×8マスのチェスボードと、64枚のコインが入ったビンがある。
・看守は一枚ずつコインを取り、チェスボードの正方形のマスにコインを置いていく。
・コインはランダムに置かれる。
・あるコインは表で、あるコインは裏だ。（64枚全部表かもしれないし、全部裏かもしれない。看守は気まぐれに置くので、予測することは完全に不可能だ）
・あなたがコインの配置に干渉しようとしたら即死。
・あなたができるのは、看守がコインを気まぐれに置いていくのをじっと見ることだけ。
・すべてのコインが置かれたら、看守は64の正方形のマスのうちどれかを「ハイこれ！」っつって指差します。この正方形のマスの場所がすべての鍵になります。
・看守は、あなたに以下の行動を許します。
チェスボードの64枚のコインのうち、ひとつだけ裏返す。
1回だけ。
どれでも裏返せるけど、どれか1枚を1回だけ。
表のコインを選んだらそれを裏にできるし、逆もまたしかり。
初期状態から加えられる変更は、たったそれだけ。
・その後、あなたは部屋から追い出される。
・その後、あなたの友人が部屋に入る。
・友人は、チェスボードの状況を見て（触れることはNo）、看守が「ハイこれ！」っつって指し示した正方形のマスの場所を当てなければならない。
・チャンスは1回だけ。
・正解したら2人とも無罪放免。間違ったらただちに死刑執行
・看守はあなたたち2人にルールを説明した後、あなたたち2人に「どのコインを裏返すか」等についての戦略を練る時間を十分に与える。
戦略は？ どうやって脱出する？
そもそもこれ戦略とか決められるの？
パッと見、この問題を解くのは不可能に思えます。
看守の行動をコントロールすることはできません。
コインを裏返す前のチェスボードにどのようにコインが置かれるのかは、あらゆる可能性が考えられます。
さらに面倒なことに、「看守がどの正方形のマスを指し示すのか」は直前まで全く分かりません。
看守が指し示す可能性のあるマスは64個。
有り得る正解の数は2^6個。
正解のマスをきっちり伝えるためには6ビット（64通り）の情報量が必要になります。
「コインを裏返す」という行為には（表から裏、裏から表の）2通りの状態が存在することから、1枚のコインを裏返すことには1ビットの情報量があると言えます。
コインを裏返す前のチェスボードの状態を伝える手段はないので、友人に「どのコインを裏返したのか」を伝えることはできません。
たとえば、友人が部屋に入ったとき、表のコインが63枚、裏のコインが1枚だったとしたら、それが「元々表のコインは64枚だった」のか「元々表のコインは62枚、裏のコインは2枚だった」のかの判別すら彼にはつけられないのです。
たったひとつのコインを裏返すことで6ビットの情報を伝えることは可能なのか？
チェスボードのコインの初期状態がどんな場合でも、看守がどんなに意表をついたマスを指し示したとしても、たった1回でこの難問に100%正解する方法が存在します。
全く頭をひねることなくさっさと解答だけ読んじゃった人も、ちょっとでいいから考えてみてくださいね！！！
（聞かれる前に答えておきますが、この解答にはいかなるトンチも、ネタ的な要素も、言葉遊びも、不条理で納得のいかない成分も含まれておりません。存在するのは、厳然たる理論に基づいた数学的解答だけです）
まずはじめに
なぜこの問題を解くことが可能なのか？
実は、あなたと友人の間で1ビット以上の情報を伝える手段が存在するからなのです。
裏返すコイン以外のボード上に存在するすべてのコインは情報を持っています。それを活用すればいいのです。
「ボードのどのマスを指し示しているのか」という情報を伝えるのに十分な情報量（6ビット）は、コインの状態をコントロールすることによって確保できます。
解答に移る前に、いくつか必要となる知識を学ばねばなりません。
2進数、排他的論理和、そしてパリティです。
これらについては簡単な紹介に留めますが、この難問の簡易版をまず解いてみるにあたり非常に重要な要素となります。
チェスボードが2マスの場合
マスが2つしかないチェスボードを考えてみましょう。
（脚注：左側のマスを「マス1」、右側のマスを「マス2」と呼ぶことにします）
看守が作れるコインの状態は4通りです。
（表,表）、（表,裏）、（裏,表）、（裏,裏）
そして、看守が指し示せるマスは2通りです。
（マス1）、（マス2）
さて、事前にルールがすべて説明されているとします。
ルール通りにいくならば、看守がマス1を指定した場合、あなたはマス1のコインを表にすればそれで充分です。
コインの初期状態は4通りありますが、「必ずどれか1枚を裏返してマス1のコインが表である状態にする」のは明らかに可能です。
（裏,裏）の時はマス1のコインを裏返し、（表,表）のときはマス2のコインを裏返せばいいわけです。
同様に、（裏,表）だったらマス1のコインを、（表,裏）だったらマス2のコインを以下略です。
さて、看守がマス2を指定した場合も同じような解決法が通用します。
マス2が指定されたら、「必ずどれか1枚を裏返してマス1のコインが裏である状態にする」のです。
つまり、上記の場合は
「マス1のコインが表なら看守が指定したのはマス1」
「マス1のコインが裏なら看守が指定したのはマス2」
というような戦略を共有しておけばいいわけです。
これで解決です！
帰納的結論
数学者（と一部のコンピュータプログラマー）なら、このチェスボードの難問を解く方法が存在することを理解できるでしょう。
2つのマスを使って1ビットの情報（看守がどちらのマスを選んだか）を符号化（※ここでは「チェスボード上に表現すること」）ができたとすると、帰納的に、4つのマスを使えば2ビットの、8つのマスを使えば3ビットの…そして8つのマスを使えば6ビット（64通り）の情報を符号化できることになります。
そう、一種の帰納法のようなものです。1からスタートして、それを入れ子にして2のべき乗数を形成していきます。
1, 2, 4, 8, 16, 32, 64
では、実際にこれをどのように活用すればいいのかを見て行きましょう。
2進数
2のべき乗を扱うにあたり、2進数というものをご紹介します。
この概念を用いると本問のチェスボードの状態は勿論、あらゆるビットの組み合わせの視覚化に役立ちます。
左の図はチェスボードです。
ここではひとまず最も左上のマスに「0」を、最も右下のマスに「63」という数字を割り振りました。
それぞれのマスには規則的に0から63までの数字が割り振られており、2進数での値も確認できます。
左図のボードのマスをクリックすると、そのマスに割り振られている数字が確認できます。
図の左下にある数字は、マスの数字を2進数で表したものです。
←クリックしてください
なおこの情報は後で使います。
パリティ
2つのマスを用いるのではなく、シンプルな例のように、2進数のビットパターンによるフィルタに基づいて、チェスボードを色々な組み合わせで2つに分割していきましょう。
我々の区画は2乗の集合体なので、コインのすべてを表にすることはできません。（できるのはコイン1枚を裏返すことだけ）
かわりに、ある区画のコインを1枚裏返します。
で、興味のある区画内で表になっているコインの枚数を数えられます。
で、その総数が奇数だったら1、偶数だったら0、と定義しましょう。
で、当然の話ではありますが、ある区画内のコインを（どれでも構わないので）1枚反転させると、その区画内の表コインの枚数は、奇数から偶数に（あるいは偶数から奇数に）なります。（奇数や偶数から1をマイナスすれば、その偶奇は逆になりますね）
これがパリティの概念です。このように、1ビットをプラスする、あるいはマイナスすることによって、ある状態を別の状態に変えることは、コンピュータの世界では死ぬほど頻繁に使われています。
ある区画の表コイン枚数が奇数なら、1のパリティを持つ。
ある区画の表コイン枚数が偶数なら、0のパリティを持つ。
ある区画のパリティを変えるには、ある区画内のコインを1枚反転させるだけでいい。
2乗のマスクを用いると、チェスボードを2つの区画に分ける方法がたくさん出てきます。
下の図は、平方数のビットの有無に基づいてチェスボードを分割した図です。
つまりどういうことか？
下図のフィルタを重ね合わせることにより、すべてのビットのパリティを自由自在に変更することができる1マスを特定することが可能になるわけです。
20のフィルタは、（2進数）000001との論理和（AND）であると見なせます。
21は000010との論理和、22は000100との論理和…そして25は100000との論理和。
これらの定義により、チェスボードの各マスにはひとつひとつに固有のビットパターンが存在することになります。
ビットの重なり具合のパターンを知ることで、1枚のコインを裏返すことにより、あらゆるフィルタの組み合わせにおいてパリティを変更することが可能になるわけです。
さあ、少しずつ正解が見えてきましたね？
看守が作成したチェスボードは、その時点でパリティを有しています。
コインはランダムに置かれますが、私たちは上記の6つのフィルタに基づくパリティパターンと特定区画の表コインの枚数を計算で導き出せばいいのです。
チェスボードに存在する64マスのいずれかを指定するためには6ビットの情報量が必要ですが、チェスボードのパリティを使えばそれも符号化が可能です。
「64個のコインはどれでも反転させられるし、それによって64個ある数字の全ビット（全桁）を自由自在に操作することができる」ことが分かりました。
残された課題はたったひとつ。
「パリティの組み合わせを変更して希望通りの数字（正解となるマス目に割り振られた数字）を示すためには、どの数字の場所にあるコインを反転すればいいのか？」
正解まであと一歩です！
全部一緒に
下図のクリック可能なモデルをご覧ください。チェスボードを模したものです。
左側のチェスボードは、看守が指定するマスの数字が確認できるものです。
どこかのマスをクリックすると右下に赤文字の数字（Target=○）が表示されますが、その数字がそのマスに割り当てられている数字です。左下に出るのは、その数字を2進数に直したものです。
この数字を表現することが最終的な目的になります。
とりあえずクリックして雰囲気をつかんでください。
右側のチェスボードは、コインが置かれている様子を示しています。
見やすくするために、「コインが表示されているマス」には「表コインが置いてある」、「何も表示されていないマス」には「裏コインが置いてある」という仕様になっています。
ボード上にはランダムにコインが配置されています。各マスをクリックすることで、コインの表示を切り替えられます。
右側にある2つのボタンをご覧ください。
“Random”ボタンを押すと、チェスボード上にコインがランダムに配置されます。
“Clear”ボタンを押すと、チェスボード上のコインがすべて非表示に（つまりすべて裏コイン状態に）なります。リセットボタンみたいなものです。
とりあえずクリックしまくって雰囲気をつかんでください。
さて、右側チェスボードの左下にある灰色の数字は、その状態におけるパリティを示しています。
そして、チェスボード上の緑の枠で示されたマスこそが、コインを反転させるべきマスです！
右下に緑色で示された数字（Flip=○）は、コインを反転させるべきマスに割り振られた数字を示すもので、左下の緑色の数字はそれを2進数に直したものです。
（脚注：看守が指定する数字（Target=○）を選択するのが左側チェスボード、その数字を表現するためにはどんなコインの配置のときにどのマス（Flip=○）のコインを反転させればいいのかを示すのが右側チェスボードです。2つのチェスボードは連動しています）
「コインを反転させるべきマス」をどうやって計算したのか？
（脚注：以下では、上記の「右側チェスボード」のことを便宜上「チェスボードB」と呼称します）
チェスボードB左下の灰色の数字は、チェスボードBに配置されたコインの状態をパリティ化したものです。
数字の各桁は、2乗のフィルタパターンに基づいて、コインの有無を表しています。
繰り返しになりますが、チェスボードB左下の灰色の数字は、コインの状態に基づくパリティ（初期状態におけるパリティ）です。
6つの2乗フィルタを用いることで、各区画における表コイン枚数の総数が奇数なのか偶数なのかは簡単に分かります。
特定の桁に1の値があれば、その桁を指し示す2乗フィルタの区画の表コイン枚数の総数は奇数なわけです。
チェスボードBの緑色の数字は、その数字の位置のマスのコインの状態を変えれば、チェスボード全体のパリティが最終目的である数字（Target=○）を表すように変更されるというものです。
そのマスだけが、ランダムなコインの初期状態から望むべき数字を得られるたったひとつの冴えた”スクエア”なのです。
肝心のそれを計算で導く方法ですが、チェスボードにBにおける初期状態のパリティと、最終目的である数字のXOR（排他的論理和）により求められます。
XOR―排他的論理和―
XOR（排他的論理和）とは”one or the other, but not both”（どちらか一方、ただし両方ともではない）を意味する演算子で、コンピュータプログラミングにおいて多用されています。
この演算子には、興味深い特性がいくつかあります。
XOR演算を2回繰り返すと、元の値に戻ります。
例： (A XOR B) XOR B = A
また、元となるビット列に対し、全桁に1がセットされた数でXOR演算を行うと、元のビット列のすべてのビットが綺麗に反転します。
特定のビットはそのままで、特定のビットを反転させるXOR演算がこの問題では重要になってきます。
さて、上記の特性によって、XOR演算を用いて「どのコインを反転させるのか」が計算できます。
チェスボード初期状態のパリティの各ビット（各桁）の値が（最終目的となる数値パリティの各桁の値と比べて）正しい値が既に入っていた場合、その値をそのまま保持すればいいわけですから、そのビットには0をセットしてXOR演算を行います。違う値が入っていたら、ビット反転を行う必要があるので、1をセットしてXOR演算を行います。
例：
看守が指定したマスが41（2進数で101001）でチェスボード初期状態のパリティが010101の場合
101001 XOR 010101 = 111100
111100は10進数で60。
つまりこの場合、60という数字が割り振られたマスのコインを反転させればいいわけです。
XOR演算は相互作用的にはたらくので、このプロセスの逆を辿って初期状態のチェスボードのパリティを導くことも可能です。
初期状態の表コインの場所の数字を2進数化してすべてXOR演算するだけです。なんてクールなんだ！
数学は、あなたの命を救う！
