一个博弈题的证明

看Game Theory的时候看到的这个题目:

一共有N堆石子,每堆石子的数目告诉你,然后两个人轮流从中取石子,每次最多从K堆中取,每堆取的石子数任意,每次最少取一颗石子.假设两个人都足够聪明的话,最后没石子可取的人算输,问先手和后手谁输谁赢.

以前看到这个题目的时候只是按照提示证了一下,知道这个是正确的,但是如果不知道结果的话,可能就不知道怎么想了.后来给别人讲这题的时候,突然想起其实这个题就是两个简单的博弈题的结合:报数问题,和简单的取石子游戏问题.

首先我们知道报数问题是给一个数N,每个人每次最多报K个数,最少报1个数,先报道N的算赢,问谁会赢.这个大家都会了,就是算N%(K+1)的结果就行了.

简单的取石子游戏就是上面的取石子游戏中K=1.也就是每次只能从1堆中取石子.这个题目大家也知道了,就是把所有的石子数目抑或起来,看结果是否为0.其实抑或就是先化成2进制,然后看相应的为加起来是否能整除2.

OK,那么如果我们每次最多取K堆石子的话,也就是说两个人每次都可以改变K+1堆石子(就像报数中两个人每次都可以报K+1个数)这样的话,我们就只要把N堆石子的数目化成2进制之后,然后对每一位都加起来,看是否整除K+1就行了.