3で割り切れたら勝ち

その他

こんな問題がありました.


二人が交互に 1 から n までの整数が書かれたボールを取っていく.
ただし, 一度取られたボールは元に戻さない.
ボールがなくなったらゲーム終了.
先手が取ったボールに書かれた数の総和が 3 で割り切れるときに先手の勝ち, そうでないときに後手の勝ちとする.
このとき, 先手に必勝法の存在する n を求めよ.

ニムの必勝法の証明を独力で行った身の上としては, 見過ごすことができない問題です.
そこで, 解いてみましたよっ.


3 で割り切れるかどうかが焦点なので, 1 から n までの数それぞれを, 3 で割った余りと同一視して考えます.
つまり, 3 を法として考えます.
すると, 0, 1, 2 を取っていくゲームになりますが, 0 は取っても総和が変わらないという意味で, 1 と 2 とは趣が異なります。
そこで, 0 の個数で場合分けをして考えます.
二人のゲームなので, 0 の個数が偶数か奇数かで場合分けをすれば良さそうです.
0 の個数が偶数なのは n = 6m, 6m+1, 6m+2 のときで,
0 の個数が奇数なのは n = 6m+3, 6m+4, 6m+5 のときですね.
というわけで, この 6 パターンを調べてみます.
それから, 以下では簡単のため, 先手を A, 後手を B と呼ぶことにします.


はじめに, 次の便利な事実を確認しておきます.


0, 1, 2 の個数を (a, b, c) などと書くことにする.
初期状態が (2a, 2b, 2c) のとき, 双方ともにある戦法が存在して, 最終状態で A が (a, b, c), B も (a, b, c) となるようにできる.
(このような状態を平衡状態と呼ぶことにする.)

【証明】
B については簡単.
A と同じものを取り続ければ良い.
A については, 最初に適当に選んで取ったあと, B と同じものを取り続けていく.
すると, 例えば A が最初に 0 を取った場合, B が最後の 0 を取ったときに, A は 0 を取ることができなくなってしまう.
このとき, A と B は 1 と 2 は同数ずつ取っており, さらに条件から 0 も同数ずつ取っていることになるので, これは平衡状態である.
ここからまた同様の戦法を繰り返すことにより, 最終状態も平衡状態となる.


双方ともに平衡状態にもっていくための戦法が存在することが, このゲームの必勝法を考える上での肝です.
以下, この戦法のことをオウム返し戦法と呼ぶことにします.


あとは単なる場合分け.


(i) n = 6m のとき
初期状態は (2m, 2m, 2m).
A はオウム返し戦法を実行することにより, 最終状態で A が (m, m, m) となり, A の勝ち.


(ii) n = 6m+1 のとき
初期状態は (2m, 2m+1, 2m).
B がオウム返し戦法を実行したとする.
A が最後の 1 を取ったとき, それを除くと平衡状態である.
したがって, 以後は B が改めてオウム返し戦法を実行することにより, 最終状態では A が (m, m+1, m) となり, A の負け.


(iii) n = 6m+2 のとき
初期状態は (2m, 2m+1, 2m+1).
B がオウム返し戦法を実行したとする.
ただし,
A が最後の 1 を取ったときに B は 2,
A が最後の 2 を取ったときに B は 1
を取るものとする.
このとき, 最終状態では A が (m, m+1, m) または (m, m, m+1) となり, A の負け.


(iv) n = 6m+3 のとき
初期状態は (2m+1, 2m+1, 2m+1).
B がオウム返し戦法を実行したとする.
ただし,
A が最後の 0 を取ったときに B は 1 か 2,
A が最後の 1 を取ったときに B は 2,
A が最後の 2 を取ったときに B は 1
を取るものとする.
このターンで A, B が取ったものを除けば, 平衡状態となっている.
以下, B が (ii) と同様の戦略をとると, 最終状態では A が (m+1, m, m+1) または (m+1, m+1, m) となり, A の負け.


(v) n = 6m+4 のとき
初期状態は (2m+1, 2m+2, 2m+1).
A は最初に 2 を取り, 以後はオウム返し戦法を実行したとする.
すると, B はいずれ最後の 0 を取らざるをえなくなる.
このとき, A が最初に取った 2 と, B が取ったこの 0 を除くと平衡状態となっている.
ここで, A が改めてオウム返し戦法を実行すると, 最終状態では A が (m, m+1, m+1) となり, A の勝ち.


(vi) n = 6m+5 のとき
初期状態は (2m+1, 2m+2, 2m+2).
A は最初に 0 を取り, 以後はオウム返し戦法を実行すると, 最終状態では A が (m+1, m+1, m+1) となり, A の勝ち.


終了です.


まとめ.
A が必勝なのは n = 6m, 6m+4, 6m+5 のとき.
B が必勝なのは n = 6m+1, 6m+2, 6m+3 のとき.