Twitterでみかけた論理パズルを勝手に解説してみた

ちょっと前に Twitterで以下のような論理パズルをみかけたので、勝手に解説してみようと思います！！

私の知ってる論理パズルで最高難易度

頑張ったけどお手上げでした。解答知ってすごいと思った。ある程度正解には近づいてたけどもう一段階発想の大転換が必要だった。
チェス版の向きはドアの手前の面、その右、とかで指定可能です
完全に自力で解けた人いたらガチで尊敬する pic.twitter.com/RwBnGuhkNG
— 逢空れい@在野ぴえん系応用数学者になる！ (@rinnarua) January 4, 2022

問題

問題文が画像なんですが、(写経がめんどかったので) 転載しますね

読みましたか？
特に、幼女Aは1. と 2. のいずれかの操作をちょうど1度だけ 行います
(私は最初問題文を誤読してたので大事なところを強調しました)

以下、ネタバレになるので自分で考えたい人は考えてみてください

↓

前提になる知識

排他的論理和 (xor)

解説

幼女たちが事前に決めておくべきことを、4つに分けて書きます

1. 数の置き換え

1以上64以下というのは、若干都合が悪いので、0以上63以下に置き換えます
つまり、以下のことをします
* 幼女Aは、1以上64以下の数 $n$ を告げられる。
* 幼女Aは、0以上63以下の数 $n'$ をチェス盤に何かしらの方法で残す ( $n' = n-1$ )
* 幼女Bは、0以上63以下の数 $n'$ をチェス盤から何かしらの方法で読み取る
* 幼女Bは、1以上64以下の数 $n$ を回答する ( $n = n'+1$ )

64が都合が悪い理由は、6ビットに収まらない (2進数で7桁ある) のが理由です。
0～63ならばどの数もちょうど6ビットに収まります。

2. 盤に数を割り当てる

盤のマス目に0以上63以下の番号を1つずつ振ります。
以下は1例です

3. 盤で「数」を表す

さて、幼女Aが幼女Bに数を伝えるには、盤面にその数の情報を残さなければなりません。
ここで、ポーンが置いてあるマス目の番号たちの排他的論理和を $x$ とします (1つも置かれていない状態は $x=0$ とします)

例えば、以下のように $(13,34,54)$ にポーンが置かれている場合、
$x=13\oplus34\oplus54=25$ をこの盤面が表す「数」とします。

こう決めることによって、幼女たちは意思疎通の準備ができました！

4. 幼女たちの役目

幼女Aの役目

1以上64以下の数 $n$ を聞き、0以上63以下の数 $n'$ に直します
次に現在の盤面の「数」を読み取ります。つまり、ポーンの置かれているマス目の番号たちの排他的論理和を計算します。これを $x$ とします。( $0 \leq x\leq 63$ )
$x$ と $n'$ の排他的論理和を求め、 $y$ とします。( $0 \leq y \leq 63$ )
$y$ の位置が空きマスならばポーンを置きます。ポーンがあるならば取り除きます。

なぜこれで上手くいくのか気になるかと思いますが、後ほど解説します(☆)

幼女Bの役目

盤面の「数」を読み取ります。つまり、ポーンの置かれているマス目の番号たちの排他的論理和を計算します。これを $z$ とします。( $0 \leq z\leq 63$ )
1以上64の数 $z+1$ を回答します。

なぜこれで上手くいくのか？(☆)

ここが最も大事で、最もおもしろいです。
幼女A は、 $y=x \oplus n'$ となる $y$ を求めました。
$y$ の位置が空きマスだった場合、ここにポーンを置きました。
幼女Bが読み取る、この盤面 $z$ はどうなっているでしょうか？
$x$ を作ったポーンの集合に $y$ を加えるのだから、 $z=x\oplus y$ になるはずですよね。
これに $y=x \oplus n'$ を代入すると、
$z=x\oplus y = x\oplus x\oplus n' = n'$ となり、求めたい数が読み取れました！
なんと初期盤面である $x$ が2回現れて相殺されています。
初期盤面はどんな配置でも良かったことがわかりますね。

また、 $y$ の位置にポーンがすでにあって取り除いた場合も、置いた場合と同じ演算で考えられます。
$y$ の位置のポーンを初期盤面から取り除いたものを $w$ として、 $x=w\oplus y$ ですよね。
両辺に $y$ をxorすると、 $x\oplus y = w\oplus y\oplus y = w$ となり、
結局 $z$ を求めたのと同じ式 $x\oplus y$ で求められます！ ( $w=z$ )