题目
你和朋友Amit面前有\(4\)只装樱桃的碗，其中分别有\(5\)颗、\(6\)颗、\(7\)颗和\(8\)颗樱桃。你和Amit轮流选择一只碗，并从中取走一颗或多颗樱桃。如果你先手，而且想确保自己拿到最后一颗樱桃，那么第一步应该从哪只碗里拿走多少颗樱桃？
分析
这是经典的Nim游戏。
把四碗樱桃的个数写成二进制：
\[ 5=101, \quad 6=110, \quad 7=111, \quad 8=1000.\]
先计算它们的异或和：
\[ 5\oplus 6\oplus 7\oplus 8=12.\]
在Nim中，先手的正确策略是：第一步把局面变成异或和为\(0\)。
如果原来四堆的异或和是\(12\)，其中一堆从\(a\)变成\(b\)以后，新的异或和就是\(12\oplus a\oplus b\)，而且我们希望它等于\(0\)，于是
\[ 12\oplus a\oplus b=0,\]
也就等价于
\[ b=a\oplus 12.\]
我们逐个看，若把某一堆从\(a\)改成\(b\)，则必须满足
\[ b=a\oplus 12,\]
而且还要有\(b<a\)，因为只能把樱桃拿走，不能增加。
分别检查：
- 若改\(5\)，则\(b=5\oplus 12=9\)，不行，因为\(9>5\)；
- 若改\(6\)，则\(b=6\oplus 12=10\)，不行；
- 若改\(7\)，则\(b=7\oplus 12=11\)，不行；
- 若改\(8\)，则\(b=8\oplus 12=4\)，可行。
这里其实还可以从二进制最高位更直观地看出来。
因为
\[ 12=1100_2,\]
它的最高位是\(8\)这一位。要把总异或和变成\(0\)，这一个最高位必须被消掉。因此，第一步一定要改动一堆在这一位上是\(1\)的樱桃堆。
而四堆里只有
\[ 8=1000_2\]
在这一位上是\(1\)；5/6/7的二进制都没有这一位。所以前\(3\)堆根本不可能作为制胜第一步，只能改装有\(8\)颗樱桃的那一堆。
进一步分析
这里也顺便说明一个更一般的事实。
在一般的Nim局面里，异或和最高位为\(1\)，并不一定意味着只有一堆在这一位上是\(1\)；它只意味着在这一位上是\(1\)的堆数是奇数个，所以可能是\(1\)个，也可能是\(3\)个、\(5\)个，等等。
如果恰好有两堆在某一位上都是\(1\)，那么这两位异或以后会变成\(0\)，因此这一位根本不会出现在总异或和里。也就是说，我们必须看的是总异或和最高的那个\(1\)位，而不是单个堆里最高的\(1\)位。
对总异或和最高的这一位来说，在这一位上是\(1\)的堆数一定是奇数，因此至少有一堆可以被选来修改；而且对任何这样一堆\(a\)，把它改成\(a\oplus S\)（这里\(S\)是原来的总异或和），都会得到一个更小的数，因为\(a\)和\(S\)在最高这一位上都是\(1\)，异或后这一位会被消掉，所以新数一定变小。
接着，这一堆改完以后必须满足新异或和为\(0\)，因此它的新大小只能是
\[ 8\oplus 12=1000_2\oplus 1100_2=0100_2=4.\]
所以唯一的制胜第一步是：\(8\to 4\)，也就是从装有\(8\)颗樱桃的碗里拿走\(4\)颗。
这时局面变成\(5,6,7,4\)，其异或和为\(5\oplus 6\oplus 7\oplus 4=0\)
此后为什么对手不能继续把异或和保持为\(0\)呢？因为他每次只能改动一堆。若某一步开始时总异或和已经是\(0\)，对手把某一堆从\(a\)改成\(b\)以后，新异或和就变成
\[ 0\oplus a\oplus b=a\oplus b.\]
而由于他确实拿走了樱桃，所以\(b<a\)，从而\(b\neq a\)，于是\(a\oplus b\neq 0\)。也就是说，从异或和为\(0\)的局面出发，任何合法一步都会把它变成非零。
接下来轮到你时，只要再次把异或和调回\(0\)即可。这样一来，你每次都把“异或和为\(0\)”留给对方。最后当局面变成全\(0\)时，正好轮到对方无路可走，所以最后一个拿樱桃的人一定是你。
所以答案是：第一步应从有\(8\)颗樱桃的碗里拿走\(4\)颗。
C++程序
下面这个程序把问题推广到一般情形：输入\(n\)，再输入\(n\)个非负整数表示各个碗里的初始樱桃数。计算机作为先手，与人类轮流操作。
如果你想直接下载源码，可以点击这里：nim_game.cpp.txt。由于GRAV通常不会直接提供.cpp文件，这里使用可下载的文本版本；下载后把文件名改回nim_game.cpp即可。
如果当前局面的异或和不为\(0\)，计算机会走出一步最优棋，把异或和变成\(0\)；如果当前局面本身就是异或和为\(0\)的必败态，那么先手其实没有必胜策略，程序就随便取走一颗樱桃作为合法一步。
#include <iostream>
#include <vector>
using namespace std;
int nimSum(const vector<int>& piles)
{
int result = 0;
for (int cherries : piles)
{
result ^= cherries;
}
return result;
}
bool allEmpty(const vector<int>& piles)
{
for (int cherries : piles)
{
if (cherries != 0)
{
return false;
}
}
return true;
}
void printPiles(const vector<int>& piles)
{
cout << "当前各碗樱桃数：";
for (int i = 0; i < static_cast<int>(piles.size()); ++i)
{
if (i > 0)
{
cout << ", ";
}
cout << "[" << i + 1 << "]=" << piles[i];
}
cout << '\n';
}
pair<int, int> computerMove(const vector<int>& piles)
{
int sum = nimSum(piles);
if (sum == 0)
{
for (int i = 0; i < static_cast<int>(piles.size()); ++i)
{
if (piles[i] > 0)
{
return {i, 1};
}
}
}
for (int i = 0; i < static_cast<int>(piles.size()); ++i)
{
int target = piles[i] ^ sum;
if (target < piles[i])
{
return {i, piles[i] - target};
}
}
return {-1, -1};
}
int main()
{
int n;
cout << "请输入碗的数量 n：";
cin >> n;
vector<int> piles(n);
cout << "请输入每只碗里的樱桃数：";
for (int i = 0; i < n; ++i)
{
cin >> piles[i];
}
cout << "\n计算机先手。\n";
while (true)
{
printPiles(piles);
int currentSum = nimSum(piles);
if (currentSum == 0)
{
cout << "当前异或和为0，说明这是一个先手必败态；计算机只能任选一步合法操作。\n";
}
pair<int, int> move = computerMove(piles);
int pileIndex = move.first;
int taken = move.second;
piles[pileIndex] -= taken;
cout << "计算机从第" << pileIndex + 1 << "只碗里拿走了" << taken << "颗樱桃。\n";
if (allEmpty(piles))
{
cout << "计算机拿到了最后一颗樱桃，计算机获胜。\n";
break;
}
printPiles(piles);
cout << "现在轮到你。\n";
while (true)
{
cout << "请输入两整数：碗的编号 和 取走的樱桃数：";
int chosenPile, removed;
cin >> chosenPile >> removed;
--chosenPile;
bool validPile = 0 <= chosenPile && chosenPile < n;
bool validTake = validPile && 1 <= removed && removed <= piles[chosenPile];
if (validTake)
{
piles[chosenPile] -= removed;
break;
}
cout << "输入不合法，请重新输入。\n";
}
if (allEmpty(piles))
{
cout << "你拿到了最后一颗樱桃，你获胜。\n";
break;
}
}
return 0;
}例如输入
4
5 6 7 8程序的第一步就会选择把\(8\)改成\(4\)，也就是取走\(4\)颗樱桃。
进一步阅读
这里用到的并不只是Nim这一个游戏的特性。
在组合博弈论里，有一个非常重要的结论，叫做Sprague-Grundy定理。它说明：任何一个有限的、公平的、正常玩法的组合游戏局面，都可以等价地看成一个Nim堆，这个堆的大小叫做这个局面的nimber或Grundy数。
如果一个局面\(P\)可以走到的后继局面是\(Q_1,Q_2,\dots,Q_k\)，那么它的Grundy数定义为
\[ g(P)=\operatorname{mex}\{g(Q_1),g(Q_2),\dots,g(Q_k)\},\]
其中\(\operatorname{mex}\)表示“没有出现过的最小非负整数”。
更重要的是：如果一个游戏可以拆成若干彼此独立的子游戏，那么整个局面的Grundy数就是这些子游戏Grundy数的异或：
\[ g(P_1+P_2+\cdots+P_k)=g(P_1)\oplus g(P_2)\oplus\cdots\oplus g(P_k).\]
因此，一个局面是必败态，当且仅当这个异或和为\(0\)。
本题正好就是最标准的Nim，所以每一碗樱桃本身就是一个Nim堆，整个局面的胜负就完全由\(5\oplus6\oplus7\oplus8\)决定。