解答

grundy 数を考えます。石の数 \(a_i\) の山、数 \(b_i\) が与えられたとき、この山の grundy 数は

• \(b_i\) が奇数のとき、\(a_i \mod 2\)
• \(b_i\) が偶数、\(a_i \mod (b_i+1) = b_i\) のとき、2
• それ以外のとき、\((a_i \mod (b_i+1)) \mod 2\)

となります。

道筋

2 人対称ゲームであるので、Grundy 数をまず疑います。パッと考えて規則性がわからなければ小さい数で実験しましょう。すると、0,1 が多く出てきて、2 がたまに出てくることがわかります。どういうときに 2 が出るのか、どういう規則性になっているのかを考えて、それをサッと証明できれば終了です。

解説

\(b_i\) が奇数のときは、\(b_i^k\) が奇数となるので、石の数が偶数のとき操作後は奇数に、奇数ならば偶数になります。よって、帰納的に石の数が \(x\) の時の grundy 数が \(x \mod 2\) となることがわかります。

\(b_i\) が偶数のときは、書き出していくと \(0,1,0,1, \dots, 0,1,2\)、長さ \(b_i+1\) の周期であるように見えます。これを示します。 石の数を \(x\) とすると、\(0 \leq x \leq b_i -1\) のときは操作が 1 減らすことのみであるので明らかです。また、\(x = b_i\) のときも明らかです。 \(b_i + 1 \leq x\) の時について、\(b_i^k \mod (b_i+1)\) は \(-1, 1\) のいずれかになります。また、\(k=0, 1\) の操作は可能なので、操作後の石の数を \(y\) とすると、\(y \equiv x-1\) か \(y \equiv x+1 \mod (b_i+1)\) となり、任意の方に操作可能です。よって、帰納的に示すことができます。 以上により、解答に書かれた、それぞれの山に対する grundy 数が証明されました。すべての山の grundy 数を xor した値が 0 でなければ先手の Alice が、0 のときは後手の Bob が勝ちます。