No.226

1行目に $00$ または $11$ が含まれる場合を考える.

1行目が $00$ だとすると2行目は $11$ でなければならない.

1行目が $00x$ だとすると2行目は $11\overline{x}$ でなければならない.

1行目が $00xy$ だとすると2行目は $11\overline{x}\overline{y}$ でなければならない.

このことから1行目に $00$ が含まれると2行目は1行目を反転したものにならなければならない. 1行目に $11$ が含まれる場合も同様である.

逆に考えると2行目以降から1行目の特定の桁を決定できる. このようにして1行目をできるだけ決定させたとき, 決定していない桁の数を $k$ とすると, 組み合わせの数は $2^k$ となる. ただし, $101010\dots$ のように $00$ も $11$ も含まない場合は除外する.

つぎに1行目が $101010\dots$ のように $00$ も $11$ も含まない場合を考える.

このとき, 2行目は $010101\dots$ のように1行目を反転させたものか, $101010\dots$ のように1行目をコピーしたものかのどちらかである. (2行目に $00$ または $11$ が含まれていると上の考察から1行目は2行目の反転となって矛盾する)

2行目のいくつかの数字が決定している場合, 1行目を反転させたものか1行目をコピーしたものかどちらが当てはまるかを調べる. どちらも当てはまらないならば矛盾となるので, このような組み合わせは存在しないことになる.

3行目以降も同様に計算する.