お願いします、こいつを倒して

http://www.transience.com.au/pearl.html
http://www.transience.com.au/pearl2.html

真珠が n 個の列に並べられている。双方は交互に真珠を取り去って行く。
一回の取り番では、いくつ真珠を取ってもいいが(全く以上取らないのはダメ)、一つの列からに限る。
最後に残った真珠を相手に取らせたほうが勝ちである。


一つの列にある真珠の数を一つの数(0 以上の整数)とし、全体の状態を n 個の数で表す。

n 個の数の XOR ってのはそれらの数を二進数表記したとき、
m 桁目が 1 になってる数が偶数の場合 m 桁目を 0 とし、奇数の場合 m 桁目を 1 とする。

例:
1000 8
0111 7
0101 5
0001 1
1011 XOR(8,7,5,1)

n 個の数の XOR が 0 の状態から
n 個のうちの 1 つの数から 1 以上の任意の数を引いたとき
XOR を取って 0 になることはない。

これは自明なんで証明は略。


n 個の数の XOR とったとき 0 以外になるなら
n 個のうちの 1 つの数からある数を引けば
XOR をとったとき 0 になるようにできる。

証明というか、具体的にどうするかというと、
n 個の数の XOR をとったとき、それが二進数で m 桁の数の場合、
n 個のなかのある数は m 桁目が 1 となっているので、(複数ある場合はどれを選んでもよい)
その数から 2^m - (n 個の数の XOR) を引けば良い。

上の例だと、XOR(8,7,5,1) は 4 桁で、n 個の数のうち 4 桁目が 1 なのは 8 なので、
1000 (8) から 10000 - 1011 = 101 (2^4 - 11 = 5) を引き 11 (3) となり、
XOR(3,7,5,1) = 0 のようになる。

上の二つによって、交互に n 個のうちのある一つの数から任意の数を引いていく場合、
一度引いた後 XOR を 0 に出来たほうは、相手がどうしようと、
常に XOR をとると 0 になる状態を保つことが出来る。

片方が引いた後 XOR が 0 になるように保ちつつ、
交互に数を引いていくと、最終的に n 個のうち 2 以上の数が 1 つだけの状態になる。
2 以上の数が 1 つの場合 XOR を取ると、0 にはならないので、
今度引くのは XOR を 0 に保っているほうということになる。
ここで n 個の数のうち 1 が偶数個なら、残った 2 以上の数から数を引く時 1 残るようにし、
奇数個なら 0 になるように引く。
そうすると、残った 1 は奇数個で、交互に引き合って行くと
最後の 1 つは XOR を 0 に保ってないほうが取らなければならなくなる。