カードめくりのパズル

またNYに滞在中。西海岸と東海岸を行ったり来たりするのはしんどい。が、この後は暫くはNYに来ることはないだろう。

さて、某所で見つけたパズル（の１バージョン）。

4人の人がいます。ある部屋に、裏にその4人の名前が書いてある4枚のカードが一列に並べておいてあります（一枚に付き、一人の名前。4人の名前は別々だとします。）一人一人順番に部屋に入っていって、自分の名前の書いてあるカードを見つけるまで、二枚までめくることが出来るとしましょう。次の人が部屋に入る時には、前の人がめくったカードは、当たり外れに関わらず、裏を下にされて、元の場所に戻されます。(だから、一人一人が見るカードの状態と配列は、全く同一。)それぞれの人は、自分が部屋の外にいる間は、部屋の中で起こっていることを全く見ることが出来ません。さて、どうすれば、「全員の人が自分の名前を見つける」という出来事の確率をなるべく大きく出来るでしょう？

注：4人は、ゲームの最中には情報を交換出来ないとする。ただし、ゲームの前に共同して戦略を立てることは可能。

さらに、 $2^k$ 人の人が、 $2^{k-1}$ 枚までめくることが出来るとしたら、どうなるか？　答えは、「続きを読む」の後。

ｎ人目の人の名前をプレーヤーｎとする。次のような戦略を考えてみよう。プレーヤー１は（左から数えて）１番目のカードを引く。それが当たりなら、あとの3枚からランダムに引く。それがプレーヤーn $\left( \neq 1 \right)$ のカードなら、２枚目にはｎ番目のカードを引く。プレーヤー2は、２番目のカードを引いて、以下同様....

こうすると、24通りの組み合わせのうち、10通りの場合に全員が自分のカードを引くことが出来る。全員が正解する確率は50%未満にしかならないはずなので、5/12というのは、かなり高い確率だ。このやり方でも既に当てられたカードを引いてしまうことがあるが（下のコメント参照）、その場合は必ず2枚目で当たるようになっているので無駄がない。例えば(1,3,2,4)とカードが並んでいる場合、プレーヤー３は2を引いてしまうが、2枚目で当たりをつかむことが出来る。

全員が正解しないのは、例えば、（1,3,4,2）のようなサイクルがある場合だ。この場合、プレイヤー２，３，４は２枚以内に自分のカードにたどり着けない。このような長さ３のサイクルが8通り、長さ４のサイクルが6通りあるので（で、それ以外の場合は全員が正解するので）、上の5/12という数字が出てくる。

$2^k$ 人の人が $2^{k-1}$ 枚までめくる場合、全員が正解できるのは、 $2^{k-1}+1$ あるいはそれ以上に長いサイクルが存在しない時だ。ここでちょっとした組み合わせの計算をしてやると、長さｍのサイクルの組み合わせが出来る確率は、1/mになっていることがわかる。だからそのようなサイクルが出来る確率は、

$\sum_{m = 2^{k-1}+1}^{2^k} \frac{1}{m}$

となって、これは近似的には $ln2^{k}-ln2^{k-1} = ln2$ 。

だから、全員が正解できる確率は、おおよそ31%( = (1-ln2) * 100)ということになる。

直観的にはこれよりうまいやり方はないはずだが、実際にこれが最適な戦略かは不明。