「博弈论论文」浅谈算法——博弈论

博弈论论文

转载说明

https://www.cnblogs.com/Wolfycz/p/8430991.html

https://www.luogu.org/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zong-ling-kai-shi-di-bo-yi-lun-post

以上是原文链接，请大家资瓷原创。

网上的博弈博客和论文有很多，但是有些没有详细的证明，仅仅是给出了结论。今天作者将一些常见的博弈论模板集中起来，给大家介绍一下博弈论中一些单一游戏的决策和常见的Nim模板与证明。

注：下列游戏都建立在双方都有最优策略的情况下，若未加以说明，则每人每次至少取一个石子。

例1：取石子游戏之一

有两个游戏者：A和B。有n颗石子。

约定：两人轮流取走石子，每次可取1、2或3颗。A先取，取走最后一颗石子的人获胜。

问题：A有没有必胜的策略？

分析：这是小学必备奥数题之一，我们可以很容易的知道，当n为0,4,8,12……时，A必定会输，因为不论A取多少，B只要和A共同取走4即可；当n不为0,4,8,12……时，A只需要将n取成4的倍数，这样就变成了B先取，B一定会输，所以A一定会赢。

经过我们的分析发现，对这个游戏而言，0,4,8,12……这些状态是对于先手的必败状态，而其他状态是对于先手的必胜状态，因此，我们现在介绍一下有关博弈的一些名词和概念

1、平等组合游戏

两人游戏。
两人轮流走步。
有一个状态集，而且通常是有限的。
有一个终止状态，到达终止状态后游戏结束。
游戏可以在有限的步数内结束。
规定好了哪些状态转移是合法的。
所有规定对于两人是一样的。

因此我们的例1提到的游戏即为一个平等组合游戏，但是我们生活中常见的棋类游戏，如象棋、围棋等，均不属于平等组合游戏，因为双方可以移动的棋子不同，不满足最后一个条件；而我们后续提到的游戏，以及博弈中的其他游戏，基本属于平等组合游戏

2、N状态（必胜状态），P状态（必败状态）

像例1的分析一样，0,4,8,12……等状态就是对于先手的P状态（必败状态），其他的则是对于先手的N状态（必胜状态）。

那么我们定义两个状态之间的转换：

所有的终止状态都为P状态
对于任意的N状态，存在至少一条路径可以转移到P状态
对于任意的P状态，只能转移到N状态

证明过于简单，这里不再赘述，我们只需要明白一点，每个人都会选择最策略即可。

当然这里所说的都是最后走步的人获胜的游戏，至于那些走到最后失败的游戏，我们在最后做了一个简单的讲解（Anti Nim）。

例2：取石子游戏之二

将例1的游戏扩展一下，我们定义一个集合 $S = {p_{1}, p_{2}, . . ., p_{k}} (k \in Z^{*}) S=\{{p_{1},p_{2},...,p_{k}}\}(k \in Z^*)$ S={p1,p2,...,pk}(k∈Z∗)，A，B在游戏的时候取走的石子数必须是集合里的数，其他条件不变。

那么，A还有必胜策略吗？

有没有必胜策略，我们关键是要找到哪些状态是P状态，哪些状态是N状态，不过，本题没有例1那么容易判断，因此我们需要引入一个新东西——SG函数，它的定义如下：

$f (v) = m e x {f (u) ∣ u 为 v 的后继状态} f(v)=mex\{f(u)|u为v的后继状态\}$ f(v)=mex{f(u)∣u为v的后继状态}

其中，mex(Minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。

$m e x (A) = m i n {k ∣ k \in ∁_{N} A} mex(A)=min\{k|k \in \complement_{N}A\}$ mex(A)=min{k∣k∈∁NA}

那么，终止状态的SG值显然为0，并且SG值为0的状态就是P状态，SG值不为0的状态就是N状态。

证明则非常显然，SG值为0的状态，说明它的所有后继状态都不为0，也就是它只能转移到非0状态，而SG值不为0的状态则不一样。那么SG值为0的状态就是必败状态的定义，SG值不为0的状态就是必胜状态的定义，所以我们只需要用集合S求出每个状态的SG值即可。

类似代码请见Pku2960 S-Nim

例3：取石子游戏之三

有n个石子，A，B两人轮流取石子，规定他们每次至多只能取当前石子总数 $⌈ \frac{s}{2} ⌉ \lceil \dfrac{s}{2}\rceil$ ⌈2s⌉个石子，问A先手是否有必胜策略

这题主要是为了加强大家对SG函数的理解，我们考虑从0开始

$S G (0) = 0, S G (1) = 1, S G (2) = 0, S G (3) = m e x {S G (3 - 1), S G (3 - 2)} = 2 SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex\{SG(3-1),SG(3-2)\}=2$ SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex{SG(3−1),SG(3−2)}=2

$S G (4) = m e x {S G (4 - 1), S G (4 - 2)} = 1... SG(4)=mex\{SG(4-1),SG(4-2)\}=1...$ SG(4)=mex{SG(4−1),SG(4−2)}=1...

我们把他们列出来找下规律：

0,1

0,2,1,3

0,4,2,5,1,6,3,7

0,8,4,9,2,10…

好像有个很奇怪的规律：数列在间隔递增，上一行的数间隔着插在下一行的数中间。没错，这就是本题SG函数的规律，先手必败当且仅当SG值为0。

例4：取石子游戏之四（Nim游戏）

有n堆石子，石子数目分别为 $x_{1}, x_{2}, . . ., x_{n} x_{1},x_{2},...,x_{n}$ x1,x2,...,xn，A，B两人每次可以选一堆石子取走任意多个，问A先手是否有必胜策略。

这题相当于例2的扩展版本，由于这里有多堆石子，因此我们可以得到多个SG值，而且这些SG值必定为 $x_{1}, x_{2}, . . ., x_{n} x_{1},x_{2},...,x_{n}$ x1,x2,...,xn，那么我们怎么由这一些SG值得到整局游戏的SG值呢？

Nim游戏的神奇之处在于它的SG值和异或扯上了关系，Nim游戏中先手必败当且仅当 $x_{1} \oplus x_{2} \oplus . . . \oplus x_{n} = 0, (\oplus 为异或) x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0,(\oplus 为异或)$ x1⊕x2⊕...⊕xn=0,(⊕为异或)，那么，这个为什么是成立的？

首先， $\oplus \oplus$ ⊕满足如下定律和性质

交换律： $x \oplus y = y \oplus x x\oplus y=y\oplus x$ x⊕y=y⊕x
结合律： $x \oplus (y \oplus z) = (x \oplus y) \oplus z x\oplus(y\oplus z)=(x\oplus y)\oplus z$ x⊕(y⊕z)=(x⊕y)⊕z
拥有单位元： $0 \oplus x = x 0\oplus x=x$ 0⊕x=x
相同两数运算为0： $x \oplus x = 0 x\oplus x=0$ x⊕x=0
消除律： $x \oplus y = x \oplus z \Rightarrow y = z x\oplus y=x\oplus z\Rightarrow y=z$ x⊕y=x⊕z⇒y=z

当Nim游戏的SG值为0时，我们假定取 $x_{k} x_{k}$ xk中的某些石子，使得其变成 $x_{k}^{'} x_{k}'$ xk′，我们假设 $x_{1} \oplus x_{2} \oplus . . . \oplus x_{k} \oplus . . . \oplus x_{n} = 0 = x_{1} \oplus x_{2} \oplus . . . \oplus x_{k}^{'} \oplus . . . \oplus x_{n} x_{1}\oplus x_{2}\oplus...\oplus x_{k}\oplus...\oplus x_{n}=0=x_{1}\oplus x_{2}\oplus...\oplus x_{k}'\oplus...\oplus x_{n}$ x1⊕x2⊕...⊕xk⊕...⊕xn=0=x1⊕x2⊕...⊕xk′⊕...⊕xn，根据消除律可得， $x_{k} = x_{k}^{'} x_{k}=x_{k}'$ xk=xk′，这与我们的条件相矛盾，因此说明在取了石子之后，SG必然发生了改变；

那么对于一个SG值不为0的状态，我们必然可以通过一个操作，使得SG值变0。我们只需要找到当前SG最左端为1的一列（二进制），任意找到一堆石子使得那一列同样为1，从这堆中取走若干个石子，使得SG’值为0。这是显然可以的，因为将那一列变成0，这个数就必然变小了，对于其他列只需要把0变成1,1变成0即可。

因此，我们得到，对于Nim游戏而言，必败状态当且仅当 $x_{1} \oplus x_{2} \oplus . . . \oplus x_{n} = 0 x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0$ x1⊕x2⊕...⊕xn=0，对于其他情况，先手必能使当前局面变成必败状态。

代码请见Pku2975 Nim

例5：取石子游戏之五（Wythoff’s Game）

有两堆石子，个数为 $x_{1}, x_{2} x_{1},x_{2}$ x1,x2；A，B轮流取石子，规定要么只取一堆的任意多个，要么在两堆里取同样任意多个，问A先手是否有必胜策略。

这种情况下是颇为复杂的，普通SG函数已经无法解决这个问题。我们用 $(a_{k}, b_{k}), (a_{k} \leq b_{k}, k \in [0, n]) (a_{k},b_{k}),(a_{k} \le b_{k},k \in [0,n])$ (ak,bk),(ak≤bk,k∈[0,n])表示两堆物品的数量并称其为局势，如果甲面对 $(0, 0) (0,0)$ (0,0)，那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是： $(0, 0) 、 (1, 2) 、 (3, 5) 、 (4, 7) 、 (6, 10) 、 (8, 13) 、 (9, 15) 、 (11, 18) 、 (12, 20) (0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)$ (0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)

可以看出， $a_{0} = b_{0} = 0 a_{0}=b_{0}=0$ a0=b0=0, $a_{k} a_{k}$ ak是未在前面出现过的最小自然数，而 $b_{k} = a_{k} + k b_{k}=a_{k}+k$ bk=ak+k，奇异局势有如下三条性质：

1.任何自然数都包含在一个且仅有一个奇异局势中。
2.任意操作都可将奇异局势变为非奇异局势。
3.采用适当的方法,可以将非奇异局势变为奇异局势。

证明：

1.由于 $a_{k} a_{k}$ ak是未在前面出现过的最小自然数，所以有 $a_{k} > a_{k - 1} a_{k}>a_{k-1}$ ak>ak−1 ,而 $b_{k} = a_{k} + k > a_{k - 1} + k - 1 = b_{k - 1} > a_{k - 1} b_{k}=a_{k}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$ bk=ak+k>ak−1+k−1=bk−1>ak−1 。所以性质1，成立。
2.若只改变奇异局势 $(a_{k}, b_{k}) (a_{k},b_{k})$ (ak,bk)的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使 $(a_{k}, b_{k}) (a_{k},b_{k})$ (ak,bk)的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3.假设面对的局势是 $(a, b) (a,b)$ (a,b)，若 $a = b a=b$ a=b，则同时从两堆中取走 $a a$ a 个物体，就变为了奇异局势 $(0, 0) (0,0)$ (0,0)；如果 $a = a_{k}, b > b_{k} a=a_{k},b>b_{k}$ a=ak,b>bk，那么，取走 $b - b_{k} b–b_{k}$ b–bk个物体，即变为奇异局势；如果 $a = a_{k}, b < b_{k} a=a_{k},b<b_{k}$ a=ak,b<bk,则同时从两堆中拿走 $a_{k} - a_{b - a k} a_{k}–a_{b–ak}$ ak–ab–ak个物体，变为奇异局势 $(a_{b - a_{k}}, a_{b - a_{k}} + b - a_{k}); (a_{b–a_{k}},a_{b–a_{k}}+b–a_{k});$ (ab–ak,ab–ak+b–ak);如果 $a > a_{k}, b = a_{k} + k a>a_{k},b=a_{k}+k$ a>ak,b=ak+k，则从第一堆中拿走多余的数量 $a - a_{k} a–a_{k}$ a–ak即可；如果 $a < a_{k}, b = a_{k} + k a<a_{k},b=a_{k}+k$ a<ak,b=ak+k，分两种情况:第一种， $a = a_{j}, (j < k) a=a_{j},(j<k)$ a=aj,(j<k),从第二堆里面拿走 $b - b_{j} b–b_{j}$ b–bj即可；第二种， $a = b_{j}, (j < k) a=b_{j},(j<k)$ a=bj,(j<k),从第二堆里面拿走 $b - a_{j} b–a_{j}$ b–aj即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

而且，通过如上性质，我们可以发现， $a_{n}, b_{n} a_{n},b_{n}$ an,bn很像Beatty数列。其实， $a_{n}, b_{n} a_{n},b_{n}$ an,bn就是Beatty数列。

Beatty数列和Beatty定理：

取正无理数 $α, β \alpha,\beta$ α,β，使得 $\frac{1}{α} + \frac{1}{β} = 1 \frac{1}{\alpha}+\frac{1}{\beta}=1$ α1+β1=1

构造两个数列 $a_{n}, b_{n} a_{n},b_{n}$ an,bn，它们的通项为 $a_{n} = ⌊ α n ⌋, b_{n} = ⌊ β n ⌋ a_{n}=\lfloor{\alpha n}\rfloor,b_{n}=\lfloor{\beta n}\rfloor$ an=⌊αn⌋,bn=⌊βn⌋

那么这个数列显然是正整数序列，Beatty定理指出，两个数列都是严格递增的，并且每个正整数在两个数列中只出现一次

证明：

1.单调性：因为 $\frac{1}{α} < 1, α > 1 \frac{1}{\alpha}<1,\alpha>1$ α1<1,α>1，所以 $α n - 1 > α (n - 1) \alpha n-1>\alpha (n-1)$ αn−1>α(n−1)，所以 $a_{n} - 1 > a_{n - 1} a_{n}-1>a_{n-1}$ an−1>an−1， $b_{n} b_{n}$ bn也亦然如此。
2.完备性：我们要证明这个命题，只需要证明对于任意一个 $k, (k \in Z^{*}) k,(k \in Z^*)$ k,(k∈Z∗)，小于等于 $k k$ k的数在序列中出现了 $k - 1 k-1$ k−1次即可。
设数列 $a_{n} a_{n}$ an的前 $p p$ p项小于等于 $k k$ k（不包括 $p + 1 p+1$ p+1项），又因为每项取整前为无理数，不可能取到整数值，那么就有
${\begin{matrix} α p < k + 1 \\ α (p + 1) > k + 1 \end{matrix} \begin{cases}\alpha p<k+1\\\alpha (p+1)>k+1\end{cases}$ {αp<k+1α(p+1)>k+1
合并两式，得到 $p = ⌊ \frac{k + 1}{α} ⌋ p=\lfloor\frac{k+1}{\alpha}\rfloor$ p=⌊αk+1⌋，这就是小于等于 $k k$ k的数在 $a_{n} a_{n}$ an中的出现次数，同理，我们可以得到其在 $b_{n} b_{n}$ bn中的出现次数，那么我们有小于等于 $k k$ k的数在Beatty数列中的总出现数 $S = ⌊ \frac{k + 1}{α} ⌋ + ⌊ \frac{k + 1}{β} ⌋ S=\lfloor\frac{k+1}{\alpha}\rfloor+\lfloor\frac{k+1}{\beta}\rfloor$ S=⌊αk+1⌋+⌊βk+1⌋
注意到两个取整函数中的数都是无理数，于是我们就有严格的不等式
$(\frac{k + 1}{α} - 1) + (\frac{k + 1}{β} - 1) < S < \frac{k + 1}{α} + \frac{k + 1}{β} (\frac{k+1}{\alpha}-1)+(\frac{k+1}{\beta}-1)<S<\frac{k+1}{\alpha}+\frac{k+1}{\beta}$ (αk+1−1)+(βk+1−1)<S<αk+1+βk+1
于是有 $k - 1 < S < k + 1 k-1<S<k+1$ k−1<S<k+1，那么 $S = k S=k$ S=k，证毕。

我们回到之前的奇异局势，由于奇异局势中的 $a_{n}, b_{n} a_{n},b_{n}$ an,bn序列满足Beatty数列，那么同样满足其构造方法，即 $a_{n} = ⌊ α n ⌋, b_{n} = ⌊ β n ⌋ a_{n}=\lfloor\alpha n\rfloor,b_{n}=\lfloor\beta n\rfloor$ an=⌊αn⌋,bn=⌊βn⌋且 $\frac{1}{α} + \frac{1}{β} = 1 \frac{1}{\alpha}+\frac{1}{\beta}=1$ α1+β1=1。

因为 $a_{n} + n = (α + 1) n = b_{n} a_{n}+n=(\alpha +1)n=b_{n}$ an+n=(α+1)n=bn，所以 $\frac{1}{α} + \frac{1}{α + 1} = 1 \frac{1}{\alpha}+\frac{1}{\alpha +1}=1$ α1+α+11=1，解得 $α = \frac{\sqrt{5} + 1}{2} \alpha=\frac{\sqrt{5}+1}{2}$ α=25+1

那么，我们就得到了通项式: $a_{k} = ⌊ k * \frac{\sqrt{5} + 1}{2} ⌋, b_{k} = a_{k} + k a_{k}=\lfloor{k*\frac{\sqrt{5}+1}{2}}\rfloor,b_{k}=a_{k}+k$ ak=⌊k∗25+1⌋,bk=ak+k

所以对于任意局势，先手必败当且仅当局势为奇异局势，我们只需要用通项式判断其是否为奇异局势即可。

代码请见[SHOI2002]取石子游戏之三

例6：取石子游戏之六（Fibonacci Nim）

有一堆个数为n的石子，A，B轮流取石子，满足：

先手不能在第一次把所有的石子取完；
之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。

约定取走最后一个石子的人为赢家，问A先手是否有必胜策略。

这个和之前的Wythoff’s Game和取石子游戏有一个很大的不同点，就是游戏规则的动态化。之前的规则中，每次可以取的石子的策略集合是基本固定的，但是这次有规则：一方每次可以取的石子数依赖于对手刚才取的石子数。

这个游戏叫做Fibonacci Nim，肯定和Fibonacci数列：1,2,3,5,8,13,21,34,55,89,… 有密切的关系。如果试验一番之后，可以猜测：先手胜当且仅当n不是Fibonacci数。换句话说，必败态构成Fibonacci数列。

就像Wythoff博弈需要Beatty定理来帮忙一样，这里需要借助Zeckendorf定理（齐肯多夫定理）。

Zeckendorf定理（齐肯多夫定理）

任何正整数可以表示为若干个不连续的Fibonacci数之和。

证明：

我们以 $F i b_{n} Fib_{n}$ Fibn代表Fibnacci数列的第 $n n$ n项， $m, (m \in Z^{*}) m,(m \in Z^*)$ m,(m∈Z∗)，易知当 $m = 1, 2, 3 m=1,2,3$ m=1,2,3时，该定理都成立，那么我们运用数学归纳法：假定该定理对所有小于 $m m$ m的数都成立，我们只要证明该定理对 $m m$ m成立即可。

当 $m m$ m为 $F i b Fib$ Fib数时，该定理成立
当 $m m$ m不为 $F i b Fib$ Fib数时，设 $F i b_{p_{1}} < m < F i b_{p_{1} + 1} Fib_{p_{1}}<m<Fib_{p_{1}+1}$ Fibp1<m<Fibp1+1。
设 $m^{'} = m - F i b_{p_{1}} < F i b_{p_{1} + 1} - F i b_{p_{1}} = F i b_{p_{1} - 1} m'=m-Fib_{p_{1}}<Fib_{p_{1}+1}-Fib_{p_{1}}=Fib_{p_{1}-1}$ m′=m−Fibp1<Fibp1+1−Fibp1=Fibp1−1，即 $m^{'} < F i b_{p - 1} m'<Fib_{p-1}$ m′<Fibp−1
因为 $m^{'} < m m'<m$ m′<m，又因为归纳法假设 $m^{'} m'$ m′可以表示成不连续的Fibnacci数列之和，即 $m^{'} = F i b_{p_{2}} + F i b_{p_{3}} + . . . + F i b_{p_{t}}, (p_{2} > p_{3} > . . . > p_{t}) m'=Fib_{p_{2}}+Fib_{p_{3}}+...+Fib_{p_{t}},(p_{2}>p_{3}>...>p_{t})$ m′=Fibp2+Fibp3+...+Fibpt,(p2>p3>...>pt)且不是连续的整数，又因为 $m^{'} < F i b_{p_{1} - 1} m'<Fib_{p_{1}-1}$ m′<Fibp1−1，所以 $p_{2} < p_{1} - 1 p_{2}<p_{1}-1$ p2<p1−1，即 $p_{1}, p_{2} p_{1},p_{2}$ p1,p2也不是连续的整数。
故 $m = m^{'} + F i b_{p_{1}} = F i b_{p_{1}} + F i b_{p_{2}} + . . . + F i b_{p_{t}}, (p_{1} > p_{2} > . . . p_{t}) m=m'+Fib_{p_{1}}=Fib_{p_{1}}+Fib_{p_{2}}+...+Fib_{p_{t}},(p_{1}>p_{2}>...p_{t})$ m=m′+Fibp1=Fibp1+Fibp2+...+Fibpt,(p1>p2>...pt)且不是连续的整数，所以该定理成立

所以**Zeckendorf定理（齐肯多夫定理）**对所有的 $m, (m \in Z^{*}) m,(m \in Z^*)$ m,(m∈Z∗)都成立

Fibnacci数列的必败证明：

首先给出三个定理，之后证明需要用到:

$F i b_{n + 1} < 2 * F i b_{n} < F i b_{n + 2} Fib_{n+1}<2*Fib_{n}<Fib_{n+2}$ Fibn+1<2∗Fibn<Fibn+2

$F i b_{n + 2} < 3 * F i b_{n} Fib_{n+2}<3*Fib_{n}$ Fibn+2<3∗Fibn

$4 * F i b_{n} < 3 * F i b_{n + 1}, (4 * F i b_{n} < 3 * (F i b_{n} + F i b_{n - 1}) \Rightarrow F i b_{n} < F i b_{n + 1} < 3 * F i b_{n - 1}) 4*Fib_{n}<3*Fib_{n+1},(4*Fib_{n}<3*(Fib_{n}+Fib_{n-1})\Rightarrow Fib_{n}<Fib_{n+1}<3*Fib_{n-1})$ 4∗Fibn<3∗Fibn+1,(4∗Fibn<3∗(Fibn+Fibn−1)⇒Fibn<Fibn+1<3∗Fibn−1)

同样运用数学归纳法：

当 $i = 2 i=2$ i=2时，先手只能取1颗，显然必败，结论成立。
假设当 $i ⩽ k i \leqslant k$ i⩽k时，结论成立。
则当 $i = k + 1 i=k+1$ i=k+1时， $F i b_{i} = F i b_{k} + F i b_{k - 1} Fib_{i}=Fib_{k}+Fib_{k-1}$ Fibi=Fibk+Fibk−1。
则我们可以把这一堆石子看成两堆，简称 $k k$ k堆和 $k - 1 k-1$ k−1堆。
(一定可以看成两堆，因为假如先手第一次取的石子数大于或等于 $F i b_{k - 1} Fib_{k-1}$ Fibk−1，则后手可以直接取完 $F i b_{k} Fib_{k}$ Fibk，因为 $F i b_{k} < 2 * F i b_{k - 1} Fib_{k}<2*Fib_{k-1}$ Fibk<2∗Fibk−1)
对于 $k - 1 k-1$ k−1堆，由假设可知，不论先手怎样取，后手总能取到最后一颗。下面我们分析一下后手最后取的石子数 $x x$ x的情况。
如果先手第一次取的石子数 $y ⩾ \frac{F i b_{k - 1}}{3} y \geqslant \dfrac{Fib_{k-1}}{3}$ y⩾3Fibk−1，则这小堆所剩的石子数小于 $2 y 2y$ 2y，即后手可以直接取完，此时 $x = F i b_{k - 1} - y x=Fib_{k-1}-y$ x=Fibk−1−y，则 $x ⩽ \frac{2 * F i b_{k - 1}}{3} x \leqslant \dfrac{2*Fib_{k-1}}{3}$ x⩽32∗Fibk−1。
我们来比较一下 $\frac{2 * F i b_{k - 1}}{3} \dfrac{2*Fib_{k-1}}{3}$ 32∗Fibk−1与 $\frac{F i b_{k}}{2} \dfrac{Fib_{k}}{2}$ 2Fibk的大小。即 $4 * F i b_{k - 1} 4*Fib_{k-1}$ 4∗Fibk−1与 $3 * F i b_{k} 3*Fib_{k}$ 3∗Fibk的大小，我们已经得出后者大。
所以我们得到， $x < \frac{F i b_{k}}{2} x<\dfrac{Fib_{k}}{2}$ x<2Fibk。
即后手取完 $k - 1 k-1$ k−1堆后，先手不能一下取完 $k k$ k堆，所以游戏规则没有改变，则由假设可知，对于 $k k$ k堆，后手仍能取到最后一颗，所以后手必胜。
即 $i = k + 1 i=k+1$ i=k+1时，结论依然成立。

对于不是Fibonacci数列，首先进行分解。

分解的时候，要取尽量大的Fibonacci数。

比如分解85：

85在55和89之间，于是可以写成85=55+30，然后继续分解30,30在21和34之间，所以可以写成30=21+9，依此类推，最后分解成85=55+21+8+1。

则我们可以把 $n n$ n写成 $n = F i b_{p_{1}} + F i b_{p_{2}} + \dots \dots + F i b_{p_{k}}, (p_{1} > p_{2} > \dots \dots > p_{k}) n=Fib_{p_{1}}+Fib_{p_{2}}+……+Fib_{p_{k}},(p_{1}>p_{2}>……>p_{k})$ n=Fibp1+Fibp2+……+Fibpk,(p1>p2>……>pk)

我们令先手先取完 $F i b_{p_{k}} Fib_{p_{k}}$ Fibpk，即最小的这一堆。由于各个 $F i b Fib$ Fib之间不连续，则 $p_{k - 1} > p_{k} + 1 p_{k-1}>p_{k}+1$ pk−1>pk+1，则有 $F i b_{p_{k - 1}} > 2 * F i b_{p_{k}} Fib_{p_{k-1}}>2*Fib_{p_{k}}$ Fibpk−1>2∗Fibpk。即后手只能取 $F i b_{p_{k - 1}} Fib_{p_{k-1}}$ Fibpk−1这一堆，且不能一次取完。

此时后手相当于面临这个子游戏(只有 $F i b_{p_{k - 1}} Fib_{p_{k-1}}$ Fibpk−1这一堆石子，且后手先取)的必败态，即先手一定可以取到这一堆的最后一颗石子。

同理可知，对于以后的每一堆，先手都可以取到这一堆的最后一颗石子，从而获得游戏的胜利。

代码请见[Coci2010]HRPA

例7：取石子游戏之七（Staircase Nim）

有n堆石子，每堆石子的数量为 $x_{1}, x_{2}, . . ., x_{n} x_{1},x_{2},...,x_{n}$ x1,x2,...,xn，A，B轮流操作，每次可以选第k堆中的任意多个石子放到第k-1堆中，第1堆中的石子可以放到第0堆中，最后无法操作的人为输。问A先手是否有必胜策略。

这就是一个Staircase Nim，它其实可以通过一些转化变成我们所熟知的Nim游戏，先手必败当且仅当奇数阶梯上的石子数异或和为0，那么为什么是这样呢？

假如我们是先手，我们就按照这个方法将多余的石子从奇数堆移动到偶数堆里面。此后如果对手移动的是奇数堆，我们就继续移动奇数堆使得SG值重新变为0；如果对手移动的是偶数堆，我们就将他移动到奇数堆中的石子继续往下移。这样经过多次操作我们总能使奇数堆保持必胜状态，最后我们总可以在对手之后将石子从奇数堆移动到偶数堆，最后移动到第0堆，这样对手就不能移动了。

所以通过整个过程我们可以发现，偶数堆中的石子不会影响整个游戏的结果，只有奇数堆中的石子会影响游戏结果。

因此对这个游戏而言，先手必败当且仅当奇数堆中的石子数异或和为0。

类似代码请见Poi2004 GRA

例8：取石子游戏之八（Anti Nim）

本题为例4（Nim 游戏）的变相版本，其他条件均不变，唯独定义：取到最后一个石子的人为输。那么A先手是否有必胜策略？

这题和Nim游戏非常类似，就是输赢的条件不同，但是这个游戏的胜利状态却和Nim有一些区别，这个游戏的的胜利当且仅当：

所有堆石子数都为1且SG值为0
至少有一堆石子数大于1且SG值不为0

我们对这个游戏进行分析，将其分为两种情况：

所有堆的石子数均为1
至少有一堆石子数大于1

对于第一种情况而言，我们可以很容易得到当堆数为奇数时，先手必败，否则先手必胜。

对于第二种情况而言，我们分两种情况进行讨论：

当SG值不为0时：
若还有两堆石子数目大于1时，我们将SG值变为0即可；若只有一堆石子数目大于1时，我们总可以让状态变成有奇数个1。所以当SG不为0时，先手必胜。
当SG值为0时：
这样的话至少会有两堆石子的数目大于1，那么先手决策完之后，必定会使局面的SG值不为0，这样便到了先手必胜局。所以当SG为0时，先手必败。

代码请见[SHOI2008]小约翰的游戏

但是上述有关的推导只对于Anti Nim成立，对与Anti SG-组合游戏这个推论是不成立的，因此Anti SG-组合游戏的推论我们是需要重新证明的。不过这篇博客主要讨论单一游戏的决策问题，因此对于SG-组合游戏不予以讨论，有兴趣的读者可以参考贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》

浅谈算法——博弈论