请问现在谁会获胜?

[单选题]

有3堆火柴，分别有3,9,12根，两个人依次取火柴，每次只能取同一堆的火柴，最少拿一根，最多拿走堆内所有火柴，取走最后一根火柴，让对方无火柴可以取者为胜。请问现在谁会获胜?()

```
先手
```
```
不确定
```
```
后手
```

查看正确选项

剑已凌乱

直白一点：如果只有两堆不一样根数，如3,9。先手第一次把多的那堆拿到和少的那堆一样，（就是拿掉6），后手随便拿多少，先手在另外一堆拿同样多就能保证赢（很简单，推一下）。那么3堆的时候，先手只需要把任意一堆拿到只剩一根，那么这堆拿完需要2次，相对于2堆来说就是每人多拿一次的区别。结果还是先手赢

============另外，题目说只能拿同样一堆如果是拿完一堆才能拿下一堆那就更简单了

发表于 2016-10-26 22:03:07 回复(0)

Julius

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：
1、两名选手；
2、两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3、游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4、若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：
P-position：在当前的局面下，先手必败。
N-position：在当前的局面下，先手必胜。

他们有如下性质：
1.合法操作集合为空的局面是P-position；
2.可以移动到P-position的局面是N-position；
3.所有移动都只能到N-position的局面是P-position。

在这个游戏中，我们已经知道A[] = {0,0,...,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A[1]*A[2]*...*A[N]。并且每一次的状态转移很多。
虽然耗时巨大，但确实是一个可行方法。

不过，对于这个游戏有一个非常神奇的结论：

对于一个局面，当且仅当A[1] xor A[2] xor ... xor A[N] = 0时，该局面为P局面。

利用这个结论来解题：

3 ^ 9 ^ 12= 6, 而6 != 0。所以先手为N局面，先手胜。

对于这个结论的证明如下：
1. 全0状态为P局面，即A[i]=0，则A[1] xor A[2] xor ... xor A[N] = 0。
2. 从任意一个A[1] xor A[2] xor ... xor A[N] = k != 0的状态可以移动到A[1] xor A[2] xor ... xor A[N] = 0的状态。由于xor计算的特殊性，我们知道一定有一个A[i]最高位与k最高位的1是相同的，那么必然有A[i] xor k < A[i]的，所以我们可以通过改变A[i]的值为A[i]'，使得A[1] xor A[2] xor ... xor A[i]' xor ... xor A[N] = 0。
3. 对于任意一个局面，若A[1] xor A[2] xor ... xor A[N] = 0，则不存在任何一个移动可以使得新的局面A[1] xor A[2] xor ... xor A[N] = 0。由于xor计算的特殊性，我们可以知道，一定是存在偶数个1时该位置的1才会被消除。若只改变一个A[i]，无论如何都会使得1的数量发生变化，从而导致A[1] xor A[2] xor ... xor A[N] != 0。

以上三条满足ICG游戏中N,P局面的转移性质，所以该结论的正确性也得到了证明。

发表于 2015-10-25 22:58:34 回复(10)