一般化21ゲームは○手必勝

game

シラフの時に考えてみたら意外と簡単だったので書いてみます。

普通の21ゲームの必勝法

一度に言える数字は3個までで、21を言わせれば勝ち。この問題は逆から考えていくと良い。

  1. 相手が21を言うのは自分が20を言った時なので、自分が20を確実に言えるようにする事を考える。
  2. 3つまで数字を言えるので、20-4=16を自分で言えるようにする。この時相手が答えられるのは17,18,19のどれか。そのいずれでも20に持っていく事が出来る。
  3. 自分で16と言える為には上と同様に16-4=12を言えればよい。
  4. これを繰り返すと、自分が4の倍数の数字を言えば相手がどんな数字を言っても20にたどり着ける。
  5. これが確実に行えるのは自分が【後手】の場合である。

なので21ゲームは【後手必勝】のゲームである。

仮に必勝法を知らないランダムに答える相手に後手を譲っても、相手が勝つ確率は\frac{1}{243}しか無い。圧倒的な違いが出てくる。

一般化21ゲームの必勝法

一度に言える数字はM個までで、Nを言わせれば勝ちと言うルールにしてみる。（N>M）

  1. 自分でN-1を言えば良い。
  2. それを言う為にはN-1-(M+1)=N-Mを言えば良い。
  3. N-1がM+1の倍数の時は通常の21ゲームの時と同じ事を繰り返せば良い。
  4. (N-1)/(M+1)=Q…Rの時、Rを自分が言えば良い。(R<M+1).
  5. これを確実に言えるのは【先手】の場合である。

これから一般化21ゲームの必勝法は次の様になる。

ルール：一度に言える数字はM個までで、Nを言わせれば勝ち。
1. N-1がM+1の倍数の時、後手になりM+1の倍数を言う。【後手必勝】
2. そうではない時、先手になり(N-1)/(M+1)=Q…Rの余りRを言う。その後はM+1の倍数を足した数字を言っていく。【先手必勝】

例えば、一度に言える数字は3個までで、22を言わせれば勝ちとしてみる。その時は21/4=5…1なので先手必勝。で、自分が言うべき数字は次の通り。1,5,9,13,17,21。