No.8 N言っちゃダメゲーム

No.8 N言っちゃダメゲーム　解説

この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。

自分は必ず先攻で、相手は後攻です。

１〜Kの値までで加算して宣言することができます。

解答

この問題は自分がN−１をいうことができれば勝てます。

相手にN−１−K≦X≦N−２を相手に言わせれば良い。

自分はNー１ーKー１「Nー１ー（K＋１）」を言えば勝てます。

相手にNー１ーKー１ーK≦X≦N−１ーKー１ー１を言わせれば良い

自分はNー１ーKー１ーKー１「Nー１ー２（K＋１）」を言えば勝てます。

このように続けていくと「Nー１ーM（K＋１）」（Mは定数）を言える時自分は勝つことがでいます。逆にこの値を相手に言わせてしまうと負けになります。自分は先攻で自分の初期状態は０であるためこの値が０と等しいと自分はこの値を宣言することができません。そのような場合相手は必勝法を使うため自分は勝てません。

つまり

Nー１ーM（K＋１）＝０

が成り立つ時

すなわち

N＝M（K＋１）＋１の時

負けます。

したがって

N mod (K+1) == 1の時負けとなります。

以上解説でした。