カウントゲーム必勝法の一般化

カウントゲームの必勝法

1. カウントゲームとは
   参加者は二人。1から50まで二人でカウントしていきます。その際に最低1つ最大3つの数までカウントできるという縛りがあります。そして最終的に50をカウントしてしまった方が負けです。

2. 必勝法
   50を言ったら負けなので勝つためには自分の番で49を言う必要があります。なので次に相手にどうやって49を言わせないかを考えます。
   $$ 40\ \textcolor{blue}{41}\ 42\ 43\ 44\ \textcolor{blue}{45}\ 46\ 47\ 48\ \textcolor{blue}{49}\ 50\ $$ 　と数を並べてみました。
   最大3つカウントができるので相手に49を言わせないためには自分が45でカウントを終える必要があります。45を言うためには41とこの操作を繰り返し行います。
   49 45 41 37 33 $ \cdots $ 9 5 1 と最後は1となります。
   つまり4で割ったとき1余る数を言っていけば必勝となることが分かりました。

3. ゲームの拡張と必勝法の一般化
   参加者二人。1からNまでを二人でカウント。最低1つ最大Cつカウントができる場合を考えます。同様に勝つためには自分の番で(N-1)を言う必要があります。漸化式を考え勝敗を分ける自然数を辿っていきます。$$ a_{0}=N-1 \\ a_{n+1}=a_{n}-(C+1)　から $$
   $$ a_{n}=(N-1)-n(C+1) $$
   ここで漸化式の最小値をR(≠0)と置くと、(N-1)を(C+1)で割った時の余りもRであることが簡単に分かります。
   したがってR=0の場合は(c+1)の倍数、R≠0の場合なら(C+1)で割った時の余りがRの数でカウントを終えると必勝となります。

4. ゲームの派生
   カウントゲームと数学的に同一なものが他にもあります。

• 二人で交互に1~9までの数を言い合いそれを合計してちょうど100にした方が勝ち。

• 二人で交互に1個また2個石を積むという規則でゲームをやり初めて全体で7個になった方が勝ち。
  （石を「積む」のと「とる」は同じなので一山崩しも同一です。）
  上はN=101,C=9のカウントゲーム
  下はN=8,C=2のカウントゲームとみなすことが出来ます。