能不能解释一下[0,2,2]为什么先手必赢?

我比较同意3楼的观点：用动态规划——逆推。(动态规划有数学归纳法的思想？)


把3堆石头的数目进行排序，按小到大.
定义这样一个函数：f(x,y,z)表示3堆石头按小到大的顺序分别为x,y,z.如果函数值为偶数表示甲(先取者)负，奇数则是甲胜。
因为甲要想赢的话，必须改变x,y,z中的一个数让它变成乙必负的情况。即f(x',y',z')=偶数。

因此只要找到那些f(x,y,z)=0的那些项即可。

从f(0,0,0)考虑起：f(0,0,0)=0.
f(0,0,z)只要把z变成0(只改变一次)则有f(0,0,0)=0=偶数，故f(0,0,z) 绝不会等于偶数。
f(0,1,1)不可能只改变一个数变成f(0,0,0)，故f(0,1,1)=0.
f(0,x,x)不可能只改变一个数变成f(0,1,1)或f(0,0,0),故f(0,x,x)=0.

综上， f(0,x,x) = 0.

下面考虑3堆石头均不为0的情况。
f(1,1,1) f(1,2,2) 只要把第一个1变为0，则变成了f(0,x,x)的情况，故这两个不要考虑
f(1,2,3)随便怎么都不可能只改变一个数，变成f(0,x,x)，故f(1,2,3)=0.
f(1,2,3+x)只要把3+x变成3，既有f(1,2,3)=0. 故不要考虑f(1,2,3+x).
同理，f(1,3,x)只要把x变成2，马上就变成了f(1,2,3). 不考虑。
f(1,4,5)不可能变成f(1,2,3),也不可能变成f(0,x,x)， 故 f(1,4,5)=0.
...
综上有 ， f(1,2x, 2x+1) = 0.

f(2,3,x) 可以变成f(1,2x,2x+1)【x=1】. 故不考虑
f(2,4,5) 可以变成f(1,2x,2x+1)【x=2】, 故不考虑
f(2,4,6) 不可能变成f(1,2x,2x+1)或f(0,x,x)， 故f(2,4,6) = 0.
...
这样可以得到 f(2,y,z)=0的时候，y与z应该满足的条件。
。。。
不知道这样可不可以找到满足f(x,y,z)=0的x,y,z的一般规律。如果找到了规律，那写代码非常简单了。如果没找到，也可以模拟上面的思考过程，逆推，至少可以求出f(x,y,z).

[quote]
能不能解释一下[0,2,2]为什么先手必赢?[/quote]
0，2，1是先手赢，0，2，2是先手败。

记忆中似乎是一道微软面试题，但是解法忘了。楼主提到了一个词，“异或”。我隐约记得这是解题的关键。
想了很久也没结果，编写一个程序穷举了15以内所有的可能性，但也没有总结出什么规律来。最后还是去看了答案……

基本的方法其实前面已经讨论了，对于(0, x, x)的情形，是必败的。因为无论你取多少石头，对方就会在另一堆里面取同等数量的石头，直到最后变成(0, 0, 0)，败局注定。
其实(0, x, x)相当于只有两堆石头。如果有N堆的话，就用异或。只要保持所有的石头总数异或的结果为零即可。如果是三堆石头(x, y, z)，只要满足(x^y^z) == 0，则注定败局。
先证明如下两个命题：
命题1：对于任意的非负整数x, y, z，如果有(x^y^z) == 0，则只要减小x, y, z三个值中的任何一个，就必定使得(x^y^z) != 0
命题2：对于任意的非负整数x, y, z，如果有(x^y^z) != 0，则一定存在一种方法，减小x, y, z三个值中的某一个，使得(x^y^z) == 0

根据命题1、命题2，只要满足了(x^y^z) == 0，则无论你怎么取石头，都会使得(x^y^z) != 0，而只要你使得(x^y^z) != 0，对方就一定能找到一种办法，使得(x^y^z) == 0重新成立。如此往复，最终变为(0, 0, 0)。如此就能得出最终结论：
(x, y, z)导致失败的充分必要条件是(x^y^z) == 0。

补充A：(x^y^z) == 0我为什么要写括号？因为C语言里面==的优先级比^要高。刚才写程序的时候出错了。
补充B：命题1结论比较明显。命题2可能不太容易想到，我也不知道我这个证明是否正确：假设x<=y<=z，则(x^y^z)一定不会超过z，只要在z里面取出一部分，使得(x^y) == z即可。

没什么复杂的，这个题的关键是石头的总数是奇数还是偶数，如果是奇数，因为分成了3堆，奇数堆，先取者必赢，sarrow都分析那么清楚了，我就偷懒了。

题的过程好像很复杂，但凡interactive的题都给人这样的感觉，但其实只要抓住了变化中的不变量，神马都是浮云，这个题的不变量就是赢家状态为两堆石头相等，或者说，还剩下偶数堆石头(2n)，这个2n堆石头每堆石头数目都相等，接cowboy的话，XOR(A1, A2,...,A2n)为0，那么就赢了。
对于3堆石头的情况，由于SUM(A1+A2+A3)为奇数，所以

begin:   (A1, A2, A3)   XOR(A1, A2, A3)必为1
halfway: (A1',A2',A3')  如果XOR(A1',A2',A3')为0，且由对方取，对方改成XOR为1
hlafway':(A1'',A2'')    ...........
end:     (0,0)          胜