日経エキシビジョンH「8^kゲーム」

Pocket

「日経コンテストのエキシビジョンの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 で割った余りみたいなものを考えるのか。難しいな」

「慣れ、経験みたいなものも大きそうですね」

「やっぱり強くなるためにはたくさんの問題に触れないとダメだね」

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする