0⊕1=1であるため、連続する複数の排他的論理和の計算において、題意を証明するためには0であるビットを除いて考えてよい。ビット総数nは2以上の整数である。(1)ビット総数が偶数である場合nは2以上の偶数なので、奇数番目と偶数番目の項が1対1の1組になる組み合わせが必ず存在する。0となり、ビット総数が偶数の場合、その排他的論理和は0になる。(2)ビット総数が奇数である場合nは3以上の奇数なので、最後の項を除いて、奇数番目と偶数番目の項が1対1の1組になる組み合わせが必ず存在する。なり、ビット総数が奇数の場合、その排他的論理和は1になる。解説編ここから順を追って解答のプロセスを考察・解説していきます。考えることまず始めに、本問の前提を確認しましょう。悪魔が指定する整数は64通り。幼女側の回答のチャンスは1回きりなので、当てずっぽうだと1.5%程度の確率でしか正解しません。本問では、論理クイズであるという特性上100%正解できる解答法があるとすでに知らされています。この1.5%の賭けを100%の法則に変える何らかのプロセスが存在するのです。情報量の壁を越えろこの論理クイズにおいて最大の焦点となるのが「幼女Aは幼女Bにどうやって最大64通りの情報を伝えるのか」という問題。幼女Aにできる行動は、チェス盤の様子を見て、どれかひとつのポーンを操作することだけ。「どのポーンを操作したか」を伝達する手段はありません。そのため幼女Aが行えるのは「あるマスのポーンの状況を変えること」のみです。「ポーンを置く」「ポーンを除く」のどちらか。マスにはポーンが「置かれている」「存在しない」のいずれかしかありませんから、幼女Aの行為にはマスのポーンを「有から無へ」「無から有へ」の2通りの状態にできる性質があります。幼女Aの操作には1ビット(2通り)の情報量があると言えます。正解の可能性は「1〜64の整数いずれか」という64通り。ポーンを6つ操作できるのであれば簡単に解決できるのですが、あいにく操作できるポーンは1つのみ。すれば1ビットの変更で6ビットの情報を操れるのでしょうか?1ビットとは?いきなり「1ビット」という単語が出てきて驚いた方もいるでしょう。1ビットとはコンピュータ内部における情報表現の最小単位で、「0」か「1」が格納されます。言い換えると、1ビットとは0と1の2種類の情報表現が可能であるものです。2通りを表現できる単位です。電球はON/OFFという2つの状態があり、なおかつそれを切り替えられるので、1ビットの情報量があると言えます。この「ビット」という単位が本問では重要になります。そこで、チェス盤が2マスの場合を考えて「1ビットの威力」を見てみましょう。チェス盤が2マスの場合を考えよう問題マスが2つしかないチェス盤があります。幼女Aは部屋に入り、悪魔がランダムにポーンを置いたチェス盤を見ます。悪魔は幼女に1~2の整数のどちらかを告げ、その後幼女Aは「いずれかのマスにポーンを置く」「いずれかのマスのポーンを取り除く」のどちらかの操作を1回だけ行います。幼女Aは部屋から出ます。幼女Bは部屋に入り、チェス盤の様子を見て幼女Aに告げられた整数を当てます。この時、幼女たちはどのような戦略を取るべきでしょう?解答2つのマスをそれぞれ「1マス目」「2マス目」とします。悪魔が告げる整数は以下の2通りです。(1)、(2)悪魔が作りうるチェス盤のポーンの状態は以下の4通りです。※ポーンの有る無しをそれぞれ「○」「×」という記号で表現しています幼女たちは、「正解が1なら1マス目を○にする」「正解が2なら1マス目を×にする」という戦略を事前に共有しておきます。幼女Aは、チェス盤の初期状態に応じて以下のいずれかの操作を行います。悪魔が幼女Aに告げたのが1の場合:初期状態が(○,○)であれば、2マス目のポーンを除き(○,×)にする初期状態が(○,×)であれば、2マス目にポーンを加え(○,○)にする初期状態が(×,○)であれば、1マス目にポーンを加え(○,○)にする初期状態が(×,×)であれば、1マス目にポーンを加え(○,×)にする悪魔が幼女Aに告げたのが2の場合:初期状態が(○,○)であれば、1マス目のポーンを除き(×,○)にする初期状態が(○,×)であれば、1マス目のポーンを除き(×,×)にする初期状態が(×,○)であれば、2マス目のポーンを除き(×,×)にする初期状態が(×,×)であれば、2マス目にポーンを加え(×,○)にする幼女Bは、チェス盤の1マス目が○なら「1」、×なら「2」と答える。1ビットと6ビットいかがでしょう。2マス2整数という縛りではありますが、1度きりの操作で4通りの状況を任意の2通りに変更することができました。ポーンを1つ操作することで、1ビットすなわち21=2通りの表現が可能でした。ポーンが6つ操作できるなら、6ビットすなわち26=64通りの表現が可能になりますが、これは前提から外れてしまいます。何かうまいこと「ポーン1つの操作」に6ビット分の情報量を与えねばなりません。チェス盤という存在ところで、この問題において「ポーンがランダムに置かれたチェス盤」とは何を意味するのでしょう?チェス盤のマスは64通り。表現すべき数も64通り。ポーンの配置方法は膨大。この問題に答えがあるとするなら、「ポーンがランダムに置かれた64マスのチェス盤の状況を、6ビット分すなわち64通りに圧縮する方法」があるはずです。幼女Bはチェス盤を見て1~64の数を読み取らねばならないのですから、当然、あらゆるチェス盤の状況は最終的に64通りのいずれかにならねばなりません。なければ問題が成立しないのです。チェス盤に数字を割り振るこの問題は、幼女Aがチェス盤の初期状態を数値化することから全てがスタートします。それに先立って必要なのが、「チェス盤のマスに0~63の番号を割り振る」こと。ここではひとまず、盤の左上から右に向かって規則的に0,1,2,3...と割り振り、盤の右下端に63という番号が割り振られたことにします。視認性向上のため、チェス盤の黒白模様は省略しております。フィルタでチェス盤を色分けするチェス盤を2つに分割して、64マスを2つの領域に分けていきます。分割パターンは全部で6つ。「マスの数字を二進数にした時1が登場する桁」に基づく6つのフィルタを用意します。25フィルタマスの数字を二進数にした時、25の位に「1」が登場する数字の集合。該当する数字は32〜63。これらは二進数で表すと「100000」〜「111111」となり、必ず25の位(右から6桁目)に必ず1が存在します。24フィルタマスの数字を二進数にした時、24の位に「1」が登場する数字の集合。該当する数字は16〜31、48〜63。これらは二進数で表すと「010000」〜「011111」、「110000」〜「111111」となり、必ず24の位(右から5桁目)に必ず1が存在します。23フィルタマスの数字を二進数にした時、23の位に「1」が登場する数字の集合。該当する数字は8〜15、24〜31、40〜47、56〜63。これらは二進数で表すと「001000」〜「001111」、「011000」〜「011111」、「101000」〜「101111」、「111000」〜「111111」となり、必ず23の位(右から4桁目)に必ず1が存在します。22フィルタマスの数字を二進数にした時、22の位に「1」が登場する数字の集合。該当する数字は全部で32個。これらは二進数で表すと「000100」〜「000111」(以下略)となり、必ず22の位(右から3桁目)に必ず1が存在します。21フィルタマスの数字を二進数にした時、21の位に「1」が登場する数字の集合。該当する数字は全部で32個。これらは二進数で表すと「000010」〜「000011」(以下略)となり、必ず21の位(右から2桁目)に必ず1が存在します。20フィルタマスの数字を二進数にした時、21の位に「1」が登場する数字の集合。該当する数字は全部で32個。これらは二進数で表すと「000001」、「000011」(以下略)となり、必ず21の位(右から1桁目)に必ず1が存在します。以上のフィルタを一列に並べたものがこちらです。実際に二進数に変換したものがこちら。画像を拡大してみると、それぞれのフィルタが示す位に「1」が存在するものが青く塗られていますね。フィルタの性質ご覧のように、各フィルタによって分割された領域は、そのフィルタが示す2の階乗の位にて1が存在するものの集合体です。チェス盤右上に登場する十進数の「7」は二進数では「000111」ですが、このとき二進数で「1」が登場するのは右から3桁目、2桁目、1桁目——すなわち22の位、21の位、20の位です。7となり、二進数「000111」は十進数で「7」になるわけです。フィルタを用いるともう少し話が簡単になります。「40」のマスをご覧ください。「40」のマスが青に塗られているフィルタはどれでしょう?25フィルタと23フィルタですね。これはつまり、十進数の「40」は二進数に変換すると25の位と23の位に1が存在する「101000」という数値になることになります。フィルタの特徴さて、これらのフィルタを活用すれば64個のあらゆる整数を二進数で表現できます。ここで重要なのが、マスに書かれた0から63までの整数を表現する時、どれひとつとして同じフィルタの組み合わせを要する数字はないということです。ある数を選んだとき、二進数でその数を作るのに必要なフィルタの組み合わせはすべて異なる、とも言えます。フィルタは6枚なので、フィルタの組み合わせ方は26=64通り。マスに書かれた0から63までの64個の数字を表現する時、6枚のフィルタの組み合わせ64通りが全て網羅される。幼女がチェス盤の状況を数値化する方法。それは、「各フィルタの領域内のマスにポーンが置かれた総数」が「偶数パリティ」か「奇数パリティ」をチェックし、前者なら0、後者なら1とし、その結果を二進数と見なすというもの。意味不明ですね!詳しく解説していきます。初期状態におけるチェス盤が以下の様子であると仮定します。※○がついているマスにポーンが置いてあります各フィルタごとの領域内にいくつ○があるかを数え上げます。◯の総数が偶数なら、そのフィルタにおいて偶数パリティであるため結果は0。◯の総数が奇数なら、そのフィルタにおいて奇数パリティであるため結果は1。これらの結果をメモしておきます。して出てきた0と1を前から順番に羅列していくと、6桁の0と1が並びます。上の図でいうと「101001」ですね。この数字の羅列こそが初期状態のチェス盤を数値化したものになります。この例で言うと「101001」を十進数に直した「41」こそが初期状態のチェス盤の数値です。何が起こったのか「チェス盤を(ある方法で)色分けした領域内に存在するポーンの総数が偶数か奇数か」。この作業で行っているのはそれだけです。ひとつでもポーンの位置がズレれば「101001」という数値にはなりませんし、そもそも「101001」になるポーンの配置方法はこれ以外にも星の数ほどあります。重要なのは、この一連の作業で「101001」という6桁の数値を得られたということ。その数字は二進数と見なせること。言うと、この一連の作業で得られる可能性がある数値は「000000」から「111111」の64個で、そして幼女Aがチェス盤上に表現する数も、幼女Bがチェス盤上から読み取るべき数も、いずれも64個のいずれかであるということ。最後に、幼女Aのたった1回の操作で6つのフィルタのパリティは自由自在に変更できること。最初に、チェス盤の左上を基準にして、そこから規則的に0から63までの数字をのマスに割り振りました。次に、それを二進数にしたときの値に基づいて6つのフィルタを作成しました。このフィルタを用いれば、0から63のあらゆる数字が表現できました。最後に、フィルタの領域に存在するポーンの数が偶数か奇数かを調べ、偶数なら0、奇数なら1として、並べて二進数に見なしました。この最後のプロセスに注目してください。やったことは、たまたま得られた「101001」という数値を「これは二進数だ」と見なしただけ。そこに必然性のようなものはありません。特別な意味もありませんし、今回「101001」が得られたのは偶然です。チェス盤に割り振り始める数字を右上基準にしていたら、得られる数値は全く別のものになってしまいます。核心へ大切なのは——そしてこの論理クイズにおいてもっとも大きな意味を持つのは——この一連のプロセスを経ることによって、あらゆる初期状態のチェス盤のポーンの配置から、たったひとつの二進数の数値が見出せるということ。この数値が「各フィルタの領域内のポーンが偶数か奇数か」に基づいて得られている以上、たったひとつポーンを増減するだけで、チェス盤の状況を示す二進数を「000000」〜「111111」の64通りすべてに変更できるということ。さあ、いよいよ大詰めです!少し前にフィルタについて述べた時のことを思い出してください。6枚のフィルタにはどんな特徴がありましたか?「マスに書かれた0から63までの整数を表現する時、どれひとつとして同じフィルタの組み合わせを要する数字はない」。それから?「ある数を選んだとき、二進数でその数を作るのに必要なフィルタの組み合わせはすべて異なる」。これです!チェス盤上に存在する0〜63までの数字のすべての数が、異なる組み合わせのフィルタによって塗り分けられていました。その全ての組み合わせは、0〜63までの数字に対応していました。お分かりですね?チェス盤を数値化した二進数は、各フィルタの領域内に存在するポーンの総数が「偶数」か「奇数」かによって決まります。偶数に1を加えたら奇数に、奇数に1を加えたら偶数になります。偶数から1を引いたら奇数に、奇数から1を引いたら偶数になります。チェス盤上に存在する0〜63までの数字は、フィルタの組み合わせ64通り全てを網羅する。それぞれの領域内のポーンの数を1つ増やすか1つ減らすかだけで、チェス盤を数値化した二進数を「000000」〜「111111」のどれでも好きなように変えることができるのです。具体例を見てみましょう!上の方で挙げた例です。これに一連のプロセスを当てはめると「101001」すなわち十進数で「41」という数値が得られました。この状態で、どこかのマスに1つポーンを置く、あるいは1つ取り除く、それだけでこのチェス盤を数値化した数値を「000000」〜「111111」(十進数「0」〜「63」)のどれでも好きな数値に変えられる。それがこれまでの結論です。......十進数で「63」を示す「111111」にしたい場合は?「101001」を「111111」にするには、25、23、20の位はそのままで、24、22、21の位を「1」にする必要があります。25、23、20のフィルタのポーン合計数はそのままで、24、22、21のフィルタのポーン合計数を奇数にする必要があります。「010110」の二進数があるマスにポーンを追加あるいは取り除けばいいわけです。「010110」は十進数に直すと「22」。22のマスにあるポーンを操作すればそれで終わりです。22のマスにはすでにポーンがあるので、取り除いてみましょう。さあ、これで本当に望む数値になったのでしょうか。再度数値化して確認してみます。得られた値は「111111」。見事に十進数の「63」になっています!このようなプロセスを辿ることで、あらゆる初期状態のチェス盤は64通りに数値化され、どこかひとつのマスの状況を変えるだけで、64通りの数値にすることが可能になるのです!ポーン操作についての重要な疑問チェス盤の数値を変えたくない場合は?幼女Aには、どこかのマスに「ポーンを置く」「ポーンを取り除く」のいずれかの行動を必ず実行しなければならないという制約がありました。初期状態のチェス盤を数値化した数値を変えたくない場合はどうすればよいのでしょう?簡単です。その時は、「000000」——十進数の「0」に当たるチェス盤左上のマスのポーンの状態を変えればいいのです。確認してみてください。チェス盤左上に割り振られた「0」というマスは、いかなるフィルタの領域でもありません。このマスだけは、ポーンを置いても取り除いても、各フィルタの領域のポーンの総数は全く変わりません。左上の「0」というマスには、ポーンが有ろうが無かろうがチェス盤全体の数値は変わらないという性質があります。最初にチェス盤を数値化した後、その数値を変えたくなければ、盤左上の「0」のマスにポーン置くか取り除くかすればいいのです。ポーンを置きたいマスに既にポーンがあった場合は?ポーンを加え、あるいは取り去ることであらゆる数値を表現できることが判明しました。ポーンを置きたいマスに既にポーンが置かれていた場合は?あるいは、ポーンを取り除きたいマスにそもそもポーンが無い場合は?これに対する答えは、この論理クイズの本質に深く関わる内容です。簡潔に答えを述べるとこうなります。「あるマスにポーンを置く/取り除くという行動は、いずれもマスのポーンの数を必ず増減させるため、この問題においては本質的に同じである」。幼女Aがポーンを操作するのは、チェス盤の状況を思いのままに変えるためでした。そのために必要なのは「たった1箇所のマスにポーンを加えたり減らしたりすること」でした。「たった1マスのポーンの数を増減させること」がなぜ大事かというと、「ある領域内のポーンの総数が偶数か奇数か」によってチェス盤数値化の結果が決まるからでした。「ポーンの総数」は必ず偶数か奇数になります。偶数に+1されれば奇数になり、-1されても奇数になります。奇数に+1されれば偶数になり、-1されても偶数になります。偶数と奇数は1が増減されれば必ず偶奇が入れ替わります。「ポーンの総数」は偶数か奇数かしかありえません。「あるマスにポーンを置きたい」というのは「そのマスの偶奇を入れ替えたい」ということです。「ポーンを置きたいのに既にポーンがある状態」というのは、「そのマスの偶奇を入れ替えたい状態でなおかつマスには既にポーンがある状態」です。例外となる「000000」のマスを除いて考えると、ポーンがある状態のマスの偶奇を入れ替えるためにはポーンを+1もしくは-1すればどちらにしても必ず偶奇は入れ替わることになります。ポーンが有るマスにポーンを+1するのはルール上できません。-1するしかないのですが、結果は同じです。ポーンが無いマスからポーンを-1したい場合も同様です。以上より、「あるマスにポーンを加える」「あるマスからポーンを取り除く」という操作を必ずどちらか1回だけ行わなければならない幼女Aに課されたルールの本当の意味は、彼女にどんな状態のマスでもたった1回でそのマスの偶奇を入れ替えることを可能にさせることだと言えます。あまりにも強力な制約に思えたルールには、きちんと問題を解決するためのロジックが組み込まれていたわけですね。ここは読まなくても大丈夫です以上長々と「チェス盤を数値化しポーンを操作すべきマスを求める方法」について述べてきましたが、もっとシンプルな(そして本質的な)やり方が存在します。XOR(排他的論理和)演算を使う方法です。2の階乗フィルタ6枚を使う、偶数パリティか奇数パリティかを0と1に変換する、二進数を自在に操るために領域内の偶奇を操作する。これらの過程において使われた計算には、すべてXOR演算が絡んでいます。順を追って見ていきましょう。チェス盤を数値化するまずチェス盤の状況を数値化するプロセスですが、計算的には「ポーンがあるマスの数字をすべて抜き出して二進数変換しそれらすべてについてXOR演算を行う」の一言で事足ります。いうか、長々と述べてきたのはこれを視覚的に表現するためであって、やりたいことは最終的にこれでした。ビットごとのXOR演算の性質に「複数の数値で計算を行った際の各ビットの結果は、1であるビット総数が偶数のとき0、1であるビット総数が奇数のとき1にある」というものがありました。この性質を活用して上記の計算をよく考えてみると、フィルタや偶数奇数パリティを使ったチェス盤の数値化計算と全く同じ計算過程を辿ることになります。排他的論理和を使えば一瞬でカタがつくのです。ポーンを操作すべきマスを求めるチェス盤を数値化した値を別のものに変えたい時も、XOR演算が役立ちます。数値化したチェス盤の値は「ポーンがあるマスの数字を二進数変換してすべてにXOR演算を行った結果」でしたから、それを別の値にしたいなら、その値と目的になる数値とでXOR演算を行えば操作すべきポーンの位置の二進数が取り出せます。010110つまり「010110」、十進数で「22」となる位置にあるポーンを操作すべきだと分かります。これも、計算的にはこれまで述べてきたことと全く同じです。その他その他、「マスにポーンを加えたいのに既にポーンが置かれていたらどうするか」みたいなことも全て排他的論理和で説明できます。「ビットごとの排他的論理和は2の冪を位数とする有限体GF(2n)(※nは自然数)での加減算となりこの体において加算と減算は等しくなる」という性質を理解すれば一発です。全部XORでいいのでは?その通りです。排他的論理和を使えば、この論理クイズでやるべきことは3行でまとめられます。それだけでは「なぜそうなるのか」が分かりづらくなるため、このような迂遠な解説となりました。最後の解説ここまで読み進めてくださった方の脳内からは問題文が忘却の彼方に吹き飛んでいる可能性が大なので最後にひとつだけ注意点を述べさせてください。幼女Aと幼女Bがチェス盤から読み取れる数字は0〜63ですが、最終的に幼女Bが悪魔に答えるべき数字は1〜64の整数です。すればよいのでしょう?簡単です。チェス盤の数値化の結果を1つシフトさせればいいのです。正解が14である場合、幼女Aはチェス盤を数値化し、14から1を引いた13をチェス盤に表現します。幼女Bは、チェス盤から読み取った13に1を足した14を悪魔に答えれば正解です。実際の解答手順を辿りながら正解を見ていきます。悪魔が告げる整数は53であるとする。悪魔が設定するチェス盤の初期状態は以下であるとする。(◯の場所にポーン)1.幼女Aはチェス盤に0から63の番号を割り振る悪魔から正解となる整数53を告げられた幼女Aは、事前の打ち合わせ通りにチェス盤の64マスに0〜63の数字を割り振っていく。2.幼女Aはチェス盤の状況を数値化する幼女Aはフィルタを活用(あるいはポーンがあるマス数字すべての排他的論理和を計算)し、チェス盤を数値化した「010010」という二進数を得る。3.幼女Aはどのポーンを操作すべきか計算する悪魔が告げた整数53から1をマイナスした52という数字をチェス盤に表現しなければならない。52は二進数に変換すると「110100」。フィルタを活用(あるいは現在の数値と求める数値とで排他的論理和を計算)し、操作すべきポーンのマスは「100110」すなわち「38」であると算出する。「38」のマスには既にポーンがあるので、幼女Aはそのポーンを取り除く。4.幼女Bはチェス盤の状況を数値化する幼女Aと入れ替わりで部屋に入った幼女Bは、現在のチェス盤を幼女Aと同じプロセスで数値化する。チェス盤から読み取れる二進数は「110100」。十進数に変換すると「52」。5.幼女Bは悪魔に正解を告げる最後に、幼女Bはチェス盤から読み取った十進数「52」に+1した数「53」を正解数として悪魔に告げる。6.悪魔はニッコリするおしまい最後にここまでお読みいただきありがとうございました。この論理クイズが、殺伐とした現代社会における一抹の清涼剤となりますように。Gistさまざまな論理パズルをまとめていらっしゃるcatupperという方のGist(ソースコード共有サービス)。本論理クイズは、こちらの11番目のテキストファイル「11.2人の幼女とチェス盤の部屋」から問題文の要旨を引用いたしました。Escape?問題を見つけたまではよかったのですが、あまり知られていない問題なためか日本語での解答が見つかりませんでした。Escape?(脱出不可能?)」という記事に書かれた論理クイズの内容が本問とかなり似ていました。当記事の解説は、この「DataGenetics」の記事内の解説を参考にしています。Escape?」に書かれている論理クイズ(看守と2人の囚人)は、「最初に告げられるのが1〜64の整数ではない」「ポーンではなくコインが使われている」等の細かな違いがあり、初見での見た目上の難易度はそちらの方がやや高くなっています。(本質的には同じ問題ですが)当記事作成用にものすごくいい加減に意訳した文章を記事化しましたので、ご参考までにどうぞ。puzzle雰囲気だけ参考にしました。悪魔は8×8のチェス盤にランダムにポーン(0〜64個)を置き、どこかのマスを指定する。幼女Aはそれを見てどこか1マスに対し「ポーンを置く」「取り除く」のいずれかの行動を1回のみ行う。その後、幼女Bはチェス盤の様子を見て悪魔がどのマスを指定したのか答えねばならない。プロフィールミライジョー(@Mirai_Joe)東京在住のWebマーケター。外資系で広告運用してます。