NimGame 尼姆博弈

问题

$A$ 和 $B$ 两人轮流从 $n$ 堆物品中取出一些物品， $n$ 堆物品的数量分别为 $[ s_{1}, s_{2}, s_{3} \dots s_{n} ]$ （所有物品数量都是正整数）。

每人每次从一堆物品中至少取 $1$ 个，多则不限，最后取光所有物品的人获胜。

给定 $n$ 和 $[ s_{1}, s_{2}, s_{3} \dots s_{n} ]$ ，当我方先手，我方和对方都是高手（在能赢的情况下一定能赢），求我方是否能赢。

$(1)$ 当我方面临 $[0, 7, 0]$ 局势（有 $1$ 堆物品）时，我方必赢，因为我方可以一次把剩下一组的物品取光；

$(2)$ 当我方面临 $[0, 1, 1, 0, 0]$ 局势（有 $2$ 堆物品且均剩 $1$ 个）时，我方必输，因为我方必然留给对方只剩 $1$ 堆物品的局势；

$(3)$ 当我方面临 $[0, 1, 1, 1, 0]$ 局势（有 $3$ 堆物品且均剩 $1$ 个）时，我方必赢，因为我方必然留给对方只剩 $2$ 堆物品且均剩 $1$ 个的局势；

$(4)$ 当我方面临 $[3, 4, 5]$ 局势时，暂时无法看出我方是否必赢；

\cdots

本问题背后的数学模型叫 $Nim Sum$ ，堆数组大小的二进制和，上面 $5$ 个局势可以转化为：

\begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 7_{10} = 111_{2} \\ s_{3} = 0_{10} = 000_{2} \\ nim_{1} = 0 \oplus 7 \oplus 0 = 1 \end{matrix}

\begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 1_{10} = 001_{2} \\ s_{3} = 1_{10} = 001_{2} \\ s_{4} = 0_{10} = 000_{2} \\ s_{5} = 0_{10} = 000_{2} \\ nim_{2} = 0 \oplus 1 \oplus 1 \oplus 0 \oplus 0 = 0 \end{matrix}

\begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 1_{10} = 001_{2} \\ s_{3} = 1_{10} = 001_{2} \\ s_{4} = 1_{10} = 001_{2} \\ s_{5} = 0_{10} = 000_{2} \\ nim_{3} = 0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 = 1 \end{matrix}

\begin{matrix} s_{1} = 3_{10} = 011_{2} \\ s_{2} = 4_{10} = 100_{2} \\ s_{3} = 5_{10} = 101_{2} \\ nim_{4} = 3 \oplus 4 \oplus 5 = 2 \end{matrix}

可以看出，当我方面临 $\oplus_{i=1}^{n} s_{i} = s_{1} \oplus s_{2} \oplus \cdots \oplus s_{n} \ne 0$ 局势时必赢，否则必输。

该算法时间复杂度为 $O(n)$ 。

Last updated 5 years ago