■「日経コンテストのエキシビジョンのH問題って解いた?」
●「『 8^k ゲーム』ですか。その問題なら、ちゃんと考察して解きましたよ!」
■「僕も考えてみたんだけど、なかなか解けなくて。シンプルに解けるの?」
●「すごくシンプルですよ! 先輩に鮮やかな解法をお見せしましょう!」
■「コインが N 枚あって、そこから 8^k 枚取る操作を交互に行って、取れなくなった方が負けっていうルールだね。1 枚だけ取ることもできるから、0 枚でターンが回ってきたら負けってことだね」
●「この問題を解く前に、似たようなゲームで、もっとシンプルなものについて考えてみましょう。N 枚のコインから 1, 2, 3 枚のいずれかを取るルールにするとどうですか?」
■「その問題は聞いたことがあるな。たしか、N が 4 の倍数かどうかで変わってくるんだよね。4 の倍数にして相手にターンを渡せば、相手がどの操作をしても必ず 4 の倍数に戻せるから、最終的に 0 で相手にターンを渡すことができる」
●「相手が 1 枚取ったら自分は 3 枚、2 枚なら 2 枚、3 枚なら 1 枚ですね。こうすれば相手と自分のターンで必ず 4 減ります。N が 4 の倍数ならこれをやられて先手の負けです。そうでないなら先手が初手で4の倍数にして勝ちですね。勝ち側は、4 の倍数になるように調整すればいいです」
■「この問題が8^kゲームに関係あるの?」
●「そうなんです。この問題の解法についてもう少し考えてみましょう。4 の倍数ということは、4 で割った余りが 0 ということですよね?」
■「うん」
●「今回の操作は、 -1, -2, -3 ですが、これは 4 で割った余りを -1, -2, -3 するということですよね」
■「それはそうだね。何の言い換えにもなっていないけど」
●「この操作は、4 で割った余りを +3, +2, +1 するということにもなりますよね?」
■「そうだね。-1 と +3 とかは 4 を法として合同だからね」
●「ということは、相手の -1, -2, -3 の操作を必ず +1, +2, +3 で打ち消せるということですよね」
■「なるほど、-1 されたら -3 する というのを、 -1 されたら +1 する と解釈するんだね」
●「はい。こうすると、『相手と自分のターンで 4 減らせる』ではなく『相手と自分のターンで 4 で割った余りを不変にできる』と解釈できます」
■「 4 で割った余りで考えれば、全ての操作について、それを打ち消す操作があることになるんだね。だから不変にできると」
●「現在の枚数が 4 の倍数かを見るより、現在の枚数を 4 で割った余りが 0 かどうかを見る方が考えやすいですし、4 減らせるより不変にできるほうが考えやすいです」
■「なるほど、じゃあこの考え方を 8^k ゲームに適用すればいいのか」
■「 8^k ゲームについても、操作を打ち消す操作の組ができるような変換をすればいいんだね。これによって、枚数に関するある値を不変にできればいい」
●「そういうことですね。とはいえ、無から思いつくのは結構難しいですけどね」
■「うーん、とりあえずさっきの問題と同じように、剰余で考えてみようか。8 で割った余りは、 8^0 のときだけ 1 、それ以外の 8^k では 0 か。打ち消しにはならないなあ」
●「そうですね。ちなみに、パッと思いつく方法は 8 進数表現で Nim っぽくやる方法ですけど、これは繰り下がりの処理が面倒でダメですね」
■「 7 で割った余りは、全ての 8^k で同じか。 8 % 7 = 1 だからね。7 で割った余りはかならず 1 減るみたいだけど、だからといって何も分からないか……」
●「 7 で割った余りが 1 減るので、操作の回数が分かれば勝敗が決まりますけど、回数を決めるのが難しいですね」
■「じゃあ 9 で割った余りはどうだろう。9 ≡ -1 (mod 8) だから、9 で割った余りは、8^0 を取ればで -1、 8^1 で +1、8^2 で -1、8^3 で +1、か。これなら +1 と -1 で打ち消せそうだ!」
●「良いですね! 9 で割った余りは、+1 か -1 をすることになるので、不変にできます」
■「でも、必ずできるというわけではないよね? 1 を取る操作は常にできるけど、8 を取る操作は 8 枚以上じゃないとできないから、7 枚以下になると +1 の操作ができなくなる」
●「ということは、7 枚以下になったらその瞬間に勝敗が決まるってことですよね?」
■「そうだね。0, 2, 4, 6 枚でターンが来たら負け、1, 3, 5, 7 枚でターンが来たら勝ちだね」
●「じゃあ、ゲームの終了条件をこれに言い換えましょう。7 枚以下になった時に偶数だったら手番のプレイヤーが負けです」
■「こうすると、ゲームが続いている間は 9 で割った余りを +1 も -1 もできるんだね」
●「これでほぼ解けました」
■「えっと、9 で割った余りが 0, 2, 4, 6 になるようにターンを渡せば、相手が何をやっても打ち消せるから勝ちだね。つまり、9 で割った余りが 1, 3, 5, 7 なら勝ちだ。8 の場合はどうなるのかな」
●「 9 で割った余りが 8 の場合も、+1 して余りを 0(負け状態)にできるので、勝ちですね」
■「なるほど、余りが 8 のときに、うっかり -1 して余りを 7 にしちゃうと次に 6 にされて負けるけど、手番のプレイヤーが適切に選べば勝つんだね」
●「はい。ゲーム木でも使う考え方ですが、負け状態に変える方法が 1 つでもあれば勝ち(OR条件)、勝ち状態にしか変えられなければ負け(AND条件)、です」
■「なるほど、9 で割った余りが 1, 3, 5, 7, 8 で手番が回ってきたら、0, 2, 4, 6 に変えられるんだね。これを繰り返すと、最終的に 0, 2, 4, 6 枚のいずれかの状態で手番を渡せるから勝ちだね」
●「その通りです! ということで、N を 9 で割った余りが 1, 3, 5, 7, 8 なら先手の勝ち、0, 2, 4, 6 なら先手の負けですね」
■「こうなると実装は簡単だね。ABC の A 問題レベルだ」
●「そうですね。でも考察はハマるとなかなか抜け出せない、難しい問題です」
■「相手の操作を打ち消して不変にできるような値、今回でいうと 9 で割った余りみたいなものを考えるのか。難しいな」
●「慣れ、経験みたいなものも大きそうですね」
■「やっぱり強くなるためにはたくさんの問題に触れないとダメだね」