从威佐夫博弈看博弈论——一类有趣的整数集划分问题

clamee · 2020-08-08 11:04:07 · 个人记录

威佐夫博弈([SHOI2002]取石子游戏)

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

我们来初步分析一下这个问题：

我们认为在这个博弈中的必败状态为奇异状态（我不知道为什么要这么命名），例如 (1,2),(3,5),(4,7),(6,10)...

可以发现对于一个正整数，它会且仅会出现在一个奇异状态中。

证明：

​ 1.它仅会出现在一个奇异状态中。

​ 假设同时存在两个奇异状态 (a,b),(a,c) 满足 b<c。那么将 (a,c) 取为 (a,b) 后，此时先手必败，故 (a,c) 是先手必胜态。

​ 出现矛盾。原命题得证。

​ 2.它会出现在一个奇异状态中。

​ 假设存在一个最小的正整数 d，满足 d 不能被划分到一个奇异状态中。

​ \because 对于一个必胜态，它必须要能够到达一个必败态。\therefore 对于 b\in N^*，均存在一个 a，满足 (d-a,d+b-a) 为一个奇异状态。又 \because 1。\because a 只有有限个，b 有无限个，\therefore 矛盾。

​ 原命题得证。

这样的话，我们就将这个问题转化为了正整数集的划分问题。

贝蒂定理

贝蒂定理是解决正整数集划分问题的一个有效的手段。

设a、b是正无理数且 1/a +1/b =1。记P={ [na] | n为任意的正整数}，Q={ [nb] | n 为任意的正整数}，([x]指的是取x的整数部分)则P与Q是N+的一个划分，即P∩Q=Ø且P∪Q=N+（正整数集）。

从百度百科搬了证明过来，我觉得这个证明既严谨，又直观，所以我就不额外证一遍了。

I. 任一个整数至多在集合P或Q中出现一次

因为a、b为正且1/a +1/b=1，则a、b>1，所以对于不同的整数n，na各不相同，类似对b有相同的结果。因此任一个整数至多在集合P或Q中出现一次。

II. P∩Q为空集

现证明P∩Q为空集：(反证法)假设k为P∩Q的一个整数，则存在正整数m、n使得[ma]=[nb]=k。即>k < ma、nb<k+1，等价地改写不等式为

m/(k+1)< 1/a < m/k及n/(k+1)< 1/b < n/k。相加起来得 (m+n)/(k+1) < 1 < (m+n)/k，即 k < m+n < >k+1。这与m、n为整数有矛盾，所以P∩Q为空集。

III. Z+ = P∪Q

现证明Z+=P∪Q：已知P∪Q是Z+的子集，剩下来只要证明Z+是P∪Q的子集。(反证法)假设Z+(P∪Q)有一个元素k，则存在正整数m、n使得[ma]< k <[(m+1)a]、[nb]< k <[(n+1)b]。 由此得ma < k ≦[ (m+1)a]-1<(m+1)a -1（因为a是无理数），类似地有nb < k ≦[ (n+1)b]-1<(n+1)b -1。等价地改写为 m/k < 1/a < (m+1)/(k+1)及n/k < 1/b < (n+1)/(k+1)。两式加起来，得

(m+n)/k < 1 < (m+n+2)/(k+1)，即m+n < k < k+1 < m+n+2。这与m, n, k皆为正整数矛盾。

现在，我们就可以继续解决这个问题了。

定义一个奇异状态的排名为 a 比它小的奇异状态数量。

可以观察这个图像，会发现排名为 x 的奇异状态为 (a,a+x)，设 a=\lfloor\alpha x\rfloor，其中 \alpha 是一个正无理数。

根据贝蒂定理，我们有 \frac{1}{\alpha}+\frac{1}{\alpha+1}=1，解得 \alpha=\frac{1+\sqrt{5}}{2}。

于是我们得到了奇异状态的通项公式。

威佐夫问题的求第一次取值

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?

这个问题很简单，分别找到两类不同的取法对应的奇异状态即可。

推荐练习题：

[SHOI2002]取石子游戏

威佐夫问题 V2

HDU - 2177取（2堆）石子