威佐夫博弈

内容

有两堆各若干个物品，两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

用 $(a_k,b_k)$ $(a_k\le b_k,k=0,1,2,\dots,n)$ 表示两堆物品的数量并称其为局势。

如果甲面对 $(0,0)$，那么甲已经输了，这种局势称为奇异局势。

前几个奇异局势是：$(0,0)$，$(1,2)$，$(3,5)$，$(4,7)$，$(6,10)$，$(8,13)$，$(9,15)$。

$k$ 表示奇异局势的序号， 第一个奇异局势 $k=0$。

可以看出，$a_0=b_0=0$，$a_k$ 是未在前面出现过的最小自然数，而 $b_k=a_k+k$。

性质

1. 任何自然数都包含在一个且仅有一个奇异局势中。

由于 $a_k$ 是未在前面出现过的最小自然数，所以 $a_k>a_{k-1}$，而 $b_k= a_k+k>a_{k-1}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$。

2. 任意操作都会将奇异局势变为非奇异局势。

• 只减少奇异局势 $(a_k,b_k)$ 的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。

• 减少奇异局势 $(a_k,b_k)$ 的两个分量，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。

3. 任何一个非奇异局势都可变为奇异局势。

记当前面对的非奇异局势为 $(A,B)$。

先考虑只取一堆的情况：

• 当 $A=a_p,B=a_q$ 时，

  • 变为奇异局势 $(a_p,b_p)$ 的条件：$B>b_p$。

  • 因为 $A \le B$，所以无法变为奇异局势 $(b_q,a_q)$。

• 当 $A=a_p,B=b_q$ 时，

  • 变为奇异局势 $(a_p,b_p)$ 的条件：$B>b_p$。

  • 变为奇异局势 $(a_q,b_q)$ 的条件：$A>a_q$。

• 当 $A=b_p,B=a_q$ 时，

  • 因为 $a_p < b_p = A \le B$，所以必能变为奇异局势 $(b_p,a_p)$。

  • 因为 $A \le B = a_q <b_q$，所以无法变为奇异局势 $(b_q,a_q)$。

• 当 $A=b_p,B=b_q$ 时，

  • 因为 $a_p < b_p = A \le B$，所以必能变为奇异局势 $(b_p,a_p)$。
  • 变为奇异局势 $(a_q,b_q)$ 的条件：$A>a_q$。

只取一堆的情况下，可以发现当 $A=a_p,B>b_p$ 或 $A=b_p$ 时，必能将非奇异局势变为奇异局势。

而当 $A=a_p,B<b_p$ 时，$B-A<p \longrightarrow a_{B-A} < a_p$，一定能从两堆同时取出 $A-a_{B-A}$，变为奇异局势 $(a_{B-A},b_{B-A})$。

所以任何一个非奇异局势都可变为奇异局势。

当然，当 $A>a_{B-A}$ 且 $B>b_{B-A}$ 时，一定能从两堆同时取出 $A-a_{B-A}$，变为奇异局势 $(a_{B-A},b_{B-A})$。

一个非奇异局势可能会有多种变为奇异局势的取法。

结论

两堆物品数量分别为 $n,m$ $(n\le m)$，当 $(m-n)*\frac{1+\sqrt{5}}{2}=n$ 时，先手必败，否则先手必胜。