問題

A, Bで Nim をする。Aが先手である。Bはゲームが始まる前に山に不正をすることができ、それはそれぞれの山から 0個または1 個の石を取り除くということである。B が不正をすることによってかならず B が勝つ方法があるとき、取り除く石の最小個数を求めよ。

考え方

まず Nim の必勝判定は以下の条件で判定することができる。

各山の枚数について XOR をとった値 v が

である。

よって B が不正をして勝利するときの条件は「不正をして v を 0 にすることができる」ということになる。

さて、未知なものは、石を取り除く最小個数である。石を取り除くことによって、各山の枚数の XOR にどのような影響を及ぼすのか考える。v ≠ 0 としておく。

a_i について -1 したとき

v xor a_i xor (a_i - 1) = v xor (2^k - 1)

となる。よって v の k 番目のビットが 1 である場合は 2^(k+1)-1 となるような a_i xor (a_i - 1) の値の xor を適応させて v の k ビット目の 1 を 0 にする必要がある。

v の k ビット目が 1 になっているすべて k について、a_i の a_i xor (a_i - 1) を用いて v を 0 にすることができれば、その時の適応回数が最小回数になる。