THE PARADOX(ビートたけし、竹内薫、中村亨、コマ大数学科公認副読本らしいです)から、「閉じ込められた23人」について考察。

AB
DC
のテーブルがあり、いずれかにランプが置いてある。

23人からランダムに一人ずつ呼ばれる。この試行が繰り返される。

誰が何回呼ばれたかは(本人しか)分からない。

呼ばれた人は、ランプを縦または横に動かす(対角線や、動かさない、は不可)。

最初に皆で相談できるが、それ以後は相談できない。

皆が一回以上呼ばれたことを確認したら、メインスイッチを切る(A)。

(多分)時間制限は無い。

(多分)開始時に、どのテーブルにランプが置いてあるかは分からない。

確信を持って(A)を実行する手順があるか？

答えは、
↓
↓
↓
↓
上にあげる(DorCのとき、AorBへ動かす)人が1人(X氏とする)。X氏は、AorBにあった場合は横移動。残りの22人は、下にさげる(AorBのとき、CorDへ動かす)。ただし下にさげるのは各自最大2回まで。2回下にさげた人は、それ以後は、横移動を行う。

こうすると、下にさげる作業が43回行われると、下にさげる作業を22人皆が一回以上行ったことになる(*1)。一方、上にあげる作業は、X氏のみ。X氏が上にあげる作業を43回行う(*2)と、下にさげる作業は43回または44回行われる(開始時にランプが上=AorBのとき44回)。よって、X氏が上にあげる作業を43回行った後に呼び出され、ランプが下にあれば、全員が一回以上呼ばれた(下にさげる操作を行った)ことが確認できる。

(*1) 21人が2回行っても42回にしかならない
(*2) X氏は、AorBにあった場合は横移動するので、呼び出される回数は43より多いかもしれない

2つの状態(ランプが上にあるか、ランプが下にあるか)の切り替えに着目して、操作したかどうかを判定する、という難問。

難解なのは、初期条件(ランプがどこにあるか)まで考慮しなければならない点。初期条件が、例えばランプがCにあると判明していれば、下にさげる作業を各自1回とし、X氏が上にあげる作業を22回行えばOK。初期条件が既知でも、問題として充分だったと思います。(初期条件が既知でも、一人が状態を逆方向へ変更することでカウントする、という部分が要所になる点は変わらない)

楽天ブックスは → 【送料無料】THE　PARADOX