チェス盤と囚人の論理クイズの必勝性

0. はじめに

　素人なので温かい目で読んでいていただけると助かります！
　noteで数式を扱う練習としてチェス盤を使った論理クイズの必勝性を備忘録としてまとめる。チェス盤とは言ったものの、このクイズの本質は区別のつく64個のマスにコインを1つずつ(表裏ランダムに)置き、どれか一つを裏返すことで後続の者に1から64までの整数(64種類の整数)を伝えるというものである。この問題の(やや天下り的な)解答については世の中に溢れかえっているため気になった方には調べていただくとして、本記事では(なぜか解答の量に比してあまり書かれていない)必勝性について考える。必勝性を調べるとは$${64}$$という値を一般に$${n}$$とおきなおした場合、どの$${n}$$でこの問題が必勝となるかを考えることである。また必勝性を調べる過程で間接的ではあるものの、元の問題を(天下り的ではなく順当に)解く道筋も掴めるかと思われる。
　参考サイト; 

論理クイズ「2人の囚人とチェス盤」解説英文の意訳 - 明日は未来だ！論理クイズ「2人の囚人とチェス盤」解説英文の意訳

1. 問題文と主命題

　元の問題文については参考サイトを読んでいただきたい。はじめに触れたように本記事では必勝性に言及するため本質となる部分のみを抽出した形で問題を書き直しておく; 

問題文

　$${n}$$を正整数とする。囚人$${P_1, P_2}$$は次のゲームに参加する; 
　はじめに$${P_1}$$が区別のつく$${n}$$個のマスの置かれた部屋に入る。各マスにはコインが表裏ランダムに$${1}$$つずつ置かれており、$${P_1}$$は$${0}$$から$${n-1}$$までの$${n}$$種類の整数の中から$${1}$$つをランダムに看守から告げられる。$${P_1}$$は必ず$${1}$$個のコインを裏返した後部屋から出る。その後囚人同士でコミュニケーションをとることなく$${P_2}$$がこの部屋に入り、コインの配置を見て$${P_1}$$に告げられた整数を当てることができれば囚人たちの勝利とする。
　$${P_1, P_2}$$はゲーム開始の前に($${n}$$の値と)ゲームの内容を告げられており、作戦を立てることができるものとする。

　このゲームを$${C_n}$$とし、囚人が必ず勝利する方法が存在するとき$${C_n}$$は必勝であるとよぶものとする。そのうえで本記事では以下の命題を証明する; 

主命題

$${C_n}$$が必勝$${\iff n=2^k}$$なる非負整数$${k}$$が存在する

　コインがパリティを表現しており元の問題($${C_{64}}$$)がXORを用いて簡潔に解答できることからそれなりに予想のつく主張ではあるが$${\Rightarrow}$$の証明がやや面倒である(と筆者は思っています)。

2. 用語の定義

　問題を扱いやすくするためいくつか用語を設定する。後になぜそのようなものを定めたかについて触れるため現段階ではよく分からないものがあっても構わない; 

　$${n}$$を正整数とし集合$${\lbrack n \rbrack, X_n, Y_n, E_n}$$およびグラフ$${G_n}$$を以下で定める; 

・$${\lbrack n \rbrack \coloneqq \lbrace 0, 1, \cdots, n-1 \rbrace }$$
・$${X_n \coloneqq \lbrace b \in \lbrack 2 \rbrack ^n \mid bの成分に0が偶数個含まれる \rbrace}$$
・$${Y_n \coloneqq \lbrack 2 \rbrack ^n \setminus X_n}$$
・$${E_n \coloneqq \lbrace \lbrace b, b' \rbrace \subset \lbrack 2 \rbrack ^n \mid b, b'は1成分のみ異なる \rbrace}$$
・$${G_n \coloneqq (\lbrack 2 \rbrack ^n, E_n)}$$

3. 必勝性とグラフの関係

　なぜ上のような用語を定義したのかについて見ていこう。
　コインの裏を$${0}$$、表を$${1}$$とみなせばコインの配置は$${\lbrack 2 \rbrack ^n}$$の元と同一視できる。この意味で以下では$${\lbrack 2 \rbrack ^n}$$の元を盤面と呼ぶことにしよう。$${P_2}$$が確認できるものは部屋に入って確認した盤面のみであり、$${P_1}$$がどのコインを裏返したのかさえ知ることができない。したがって囚人達は$${\lbrack 2 \rbrack ^n}$$から$${\lbrack n \rbrack}$$へのある写像を作戦の段階で共有し、$${P_1}$$は告げられた整数を対応先に持つ盤面を作って部屋を出て、$${P_2}$$はその盤面に対応する整数を答える必要がある。
　$${1}$$つのコインを裏返すことは盤面の成分を$${1}$$つだけ変更することを意味する。したがって$${G_n}$$は盤面全体を頂点とし、1つのコイン(成分)を裏返すことで移り合う盤面同士を繋ぐことによって辺を定めることで得られるグラフである。
　$${P_1}$$が作ることのできる盤面は、与えられた盤面に隣接する盤面であるためこのような盤面の集合に名前を付けておこう。$${b \in \lbrack 2 \rbrack ^n}$$に対し、集合$${N_n(b)}$$を以下で定める; 

$$
N_n(b) \coloneqq \lbrace b' \in \lbrack 2 \rbrack ^n \mid \lbrace b, b' \rbrace \in E_n \rbrace
$$

 さてグラフ$${G_n}$$の用語で必勝性を言い換えると次のとおりである。$${C_n}$$が必勝であるとは$${\lbrack 2 \rbrack ^n}$$から$${\lbrack n \rbrack}$$への写像で、任意に与えられた盤面$${b}$$に対し、$${N_n(b)}$$の各元の対応先が$${0}$$から$${n-1}$$までの全ての整数を尽くすようなものが存在することである。$${\left| N_n(b) \right|=n}$$に注意すると、この条件は$${N_n(b)}$$に制限したとき必ず全単射になると言い換えられる。この条件を満たす$${\lbrack 2 \rbrack ^n}$$から$${\lbrack n \rbrack}$$への写像を良い写像とよぶこととする。

$${C_n}$$が必勝であるとは次の条件を満たす$${\lbrack 2 \rbrack ^n}$$から$${\lbrack n \rbrack}$$への写像(良い写像)$${f}$$が存在することである：任意の$${b \in \lbrack 2 \rbrack ^n}$$に対し$${f \mid _{N_n(b)}}$$が全単射。

4. 必要性の証明

　本記事の本題である主命題の$${\Rightarrow}$$の証明を行う。$${C_n}$$が必勝であるとし、$${f_n \colon \lbrack 2 \rbrack ^n \to \lbrack n \rbrack}$$を良い写像とする。良い写像の定義より任意の$${b \in [2]^n}$$に対し$${f_n(b) = f_n(b')}$$となる$${b' \in N_n(b)}$$がただ一つ存在する。このような$${b'}$$を$${i_n(b)}$$と定めることで$${[2]^n}$$上の対合$${i_n}$$を定める。また$${\lbrace b, b' \rbrace \in E_n}$$であれば、$${b, b'}$$のいずれか一方が$${X_n}$$の元であり、残りが$${Y_n}$$の元である。以上のことから$${[2]^n}$$の元からなる次の条件を満たす列$${S=(b_1, d_1, \cdots, b_n, d_n)}$$を考えることができる; 

$$
\begin{aligned}
&・b_1 \in X_n & \\
&・f_n(b_1) = 0  & \\
&・d_k = i_n(b_k) & (1 \le k \le n-1) \\
& ・b_{k+1} \in N_n(d_k) &(1 \le k \le n-1) \\
& ・f_n(b_k)( = f_n(d_k)) = k-1 & (1 \le k \le n)
\end{aligned}
$$

これらの条件を満たす$${2n}$$個の元からなる列を$${G_n}$$の階段とよぶことにする。階段は列であるが、以下断らない限り集合としても扱う。また上のような階段$${S}$$に対し、$${b_1}$$を$${S}$$の始点、$${d_n}$$を$${S}$$の終点とよぶ。また$${f_n}$$の制限と$${i_n}$$が全単射であることと階段の構成方法から分かるように、階段は始点か終点を定めれば一意に定まることに注意する。

　さてこのように定めた階段に関して2つの補題を示し、それらを用いて必要性の証明を行おう。

補題1
　$${S_1, S_2}$$を$${G_n}$$の相異なる階段とする。このとき$${S_1 \cap S_2 = \varnothing}$$。

(証明)
　対偶を示す。$${S_1 \cap S_2 \ne \varnothing }$$より$${a \in S_1 \cap S_2}$$なる$${a}$$が存在する。階段の構成方法より$${S_1}$$と$${S_2}$$は$${a}$$より後ろの列の並びが一致するため同じ終点を持つ。したがって$${S_1=S_2}$$である。$${\square}$$

補題2
　$${S_1, S_2, \cdots, S_l}$$を$${G_n}$$の階段とし、$${ T = [2]^n \setminus (S_1\cup S_2 \cup \cdots \cup S_l) }$$とする。このとき$${T \ne \varnothing}$$なら$${f_n(b)=0}$$かつ$${b \in X_n}$$となる$${b \in T}$$が存在する。

(証明)
　$${T \ne \varnothing}$$とする。勝手な$${a \in T}$$をとる。階段を構成する反対の手順で$${f_n}$$の値が小さくなるように隣接する辺を一意に辿っていけば、$${f_n(b)=0}$$かつ$${b \in X_n}$$となる$${b}$$に到達する。もしこの過程である$${S_i}$$と交われば、階段の構成方法の一意性から$${a \in S_i}$$となり$${a \in T}$$に反する。したがってこうして得られる$${b}$$は$${b \in T}$$を満たす。$${\square}$$

　補題2より$${[2]^n}$$に階段以外の部分が残っていれば始点となる元を必ず見つけることができ、その元を始点に持つ新たな階段を一意に得ることができる。また補題1よりこうして得られる階段は元々見つかっている階段とは交わらない。$${[2]^n}$$は有限集合なので、こうして階段を構成し続けることで$${[2]^n}$$をいくつかの階段の非交和として以下のように表すことができる; 

$$
[2]^n=\coprod_{i=1}^{l}S_i
$$

　$${|[2]^n|=2^n, |S_i|=2n}$$であるから以上より次の命題が成り立ち、必要性の証明が完了する; 

命題3
　$${C_n}$$が必勝$${\implies 2n \mid 2^n \iff}$$非負整数$${k}$$が存在し$${n=2^k}$$と表せる

5. 十分性の証明

　十分性は帰納法を用いて示す。つまり$${n}$$が非負整数$${k}$$を用いて$${n=2^k}$$と表せるとき$${C_n}$$が必勝であることを$${k}$$に関する帰納法により示す。
　$${C_n}$$を解く方法は巷で書かれている方法、即ちマスをうまくブロックで分けてXORを用いる方法を加工すれば容易に見つかるだろう。しかしこの解法や解説は解き慣れない人にとってはなぜそのような発想が生まれたのかということや、別の問題を解く際に愚直に問題にアプローチするにはどのようなことをすればよいのかということについては触れておらず、やや不親切でもある。
　これから行う証明は帰納法の性質上、直接的に解法を記述するわけではない。しかし値の小さな簡単な例から値の大きな場合の解法を構成するというプロセスは、"よくできた解法"よりは愚直で現実的なアプローチといえるかもしれない。

証明

　$${k}$$が小さい場合は$${G_n}$$を直接描いて頂点に番号を振ることで容易に良い写像を見つけることができる。$${k=0}$$の場合はかなり自明であるためここでは$${k=1}$$のとき、即ち$${n=2}$$のとき$${C_n}$$が必勝であることを示そう。
　$${G_2}$$は次のように$${4}$$つの頂点から成るグラフである; 

$$
\begin{aligned}
&(0, 0) \longleftrightarrow &(0, 1)\\
&\updownarrow &\updownarrow\\
&(1, 0) \longleftrightarrow &(1, 1)\\
\end{aligned}
$$

このグラフの各頂点に、どの頂点から見ても、隣接する$${2}$$つの頂点に$${0}$$と$${1}$$が書かれているように$${0, 1}$$を割り振ればよい。例えば上の$${2}$$頂点に$${0}$$を、下の$${2}$$頂点に$${1}$$を割り振ればよい。この割り振りが良い写像を与えている。

　ある非負整数$${k}$$について、$${n=2^k}$$で$${C_n}$$が必勝、即ち良い写像$${f_n \colon [2]^n \to [n]}$$が存在すると仮定する。$${2n=2^{k+1}}$$での必勝性を示せば良い。
　写像$${g_{n}, h_{n} \colon [2]^{n} \to [2n]}$$を以下で定める; 

$$
\begin{aligned}
& g_{n}(b)=2f_n(b) \\
& h_{n}(b)=
\left\{ \,
\begin{aligned}
& 2f_n(b) &(b \in X_n) \\
& 2f_n(b)+1 &(b \in Y_n)
\end{aligned}
\right.
\end{aligned}
$$

　$${[2]^{2n}}$$を$${[2]^n \times [2]^n}$$とみなして$${[2]^{2n}}$$の元を$${(b_1, b_2)}$$と書く。以下写像の対応先の値が$${2n-1}$$を超える場合$${2n}$$で割った余りに置き換えるものとする。$${f_{2n} \colon [2]^{2n} \to [2n]}$$を以下で定める; 

$$
f_{2n} (b_1, b_2) \coloneqq g_n(b_1)+h_n(b_2). 
$$

　こうして定めた$${f_{2n}}$$が良い写像であることを示す。それには次の命題を示せば十分である; 

命題4
　任意の$${(b_1, b_2) \in [2]^{2n}}$$と任意の$${i \in [2n]}$$に対し、$${f_{2n}(b'_1, b'_2)=i}$$となる$${(b'_1, b'_2) \in N_{2n}(b_1, b_2)}$$が存在する。

(証明)
　$${f_{2n}(b_1, b_2) = j}$$とし、$${d = i-j}$$とする。

①：$${d}$$が偶数のとき
　$${f_n}$$が良い写像であるため

$$
f_n(b'_1)=f_n(b)+ \frac{d}{2}
$$

を満たす$${b'_1 \in N_n(b_1)}$$が存在する。$${(b'_1, b_2) \in N_{2n}(b_1, b_2)}$$であり

$$
\begin{aligned}
f_{2n}(b'_1, b_2) &= g_n(b'_1)+h_n(b_2)\\
&=2f_n(b'_1)+h_n(b_2)\\
&=2f_n(b_1)+h_n(b_2)+d\\
&=f_{2n}(b_1, b_2)+d\\
&=i. 
\end{aligned}
$$

②：$${d}$$が奇数かつ$${b_2 \in Y_n}$$のとき
　$${f_n}$$が良い写像で$${N_n(b_2) \in X_n}$$であるため$${h_n}$$の定め方より

$$
h_n(N_n(b_2)) = \lbrace 0, 2, 4, \cdots, 2n-2 \rbrace
$$

が成り立つ。$${h_n(b_2) \in \lbrace 1, 3, 5, \cdots, 2n-1 \rbrace}$$であるから$${h_n(b'_2)-h_n(b_2)=d}$$を満たす$${b'_2 \in N_n(b_2)}$$が存在する。$${(b_1, b'_2) \in N_{2n}(b_1, b_2)}$$であり①の計算と同様に$${f_{2n}(b_1, b'_2)=i}$$が成り立つ。

③：$${d}$$が奇数かつ$${b_2 \in X_n}$$のとき
　②と同様の議論から

$$
\begin{aligned}
&h_n(N_n(b_2)) = \lbrace 1, 3, 5, \cdots, 2n-1 \rbrace\\
&{h_n(b_2) \in \lbrace 0, 2, 4, \cdots, 2n-2 \rbrace}
\end{aligned}
$$

を知る。したがって$${h_n(b'_2)-h_n(b_2)=d}$$を満たす$${b'_2 \in N_n(b_2)}$$が存在する。$${(b_1, b'_2) \in N_{2n}(b_1, b_2)}$$であり①の計算と同様に$${f_{2n}(b_1, b'_2)=i}$$が成り立つ。$${\square}$$