取石子游戏

2025-05-16 16:54:48
推荐回答(1个)
回答1:

在50个那堆里取32个。

这是数论中的最优策略问题,没有平均数原理。
1. 从50中取走32粒剩余18粒是正确的。
2. 算法:从其中一堆中取n个,使得剩余的所有数目正好是“必负局(此时先取必输的局面)”。
3. 所谓“必负局”是指把剩余的每一堆的数目都转化成二进制的数,然后把它们相加,规定做不进位的加法(也就是异或运算),即0+0=0,1+0=0,0+1=1,1+1=0(不进位),如果所得和是0(多个0),那么此种局势称为“必负局”。
4. “必负局”原理:一个“必负局”,一次改动任何一个数,都将不再是“必负局”,同时,任何一个“非必负局”,通过正确地减少某个数,一定能变成“必负局”,并且这种操作是唯一的。设想现在是“必负局”,假如你先取,势必把其中的某个数的1改成了0,0改成了1,一定不再是“必负局”了,而我一定可以在把它变会“必负局”。其实这样的局势,相当于偶数,你取了,必定有对应我取的,所以我一定拿到最后一个。简单的想,考虑只有两堆,那么如果原来不相等,那就是“非必负局”,先取者有必胜方式,只要取多的一堆使得两堆相等,之后你取几个,我就从另一堆取几个。

3 00011
5 00101
7 00111
19 10011
18 10010
也就是说,只有最后一堆剩18个时才能是先取必负局。
所以在最后一堆里先取32个。