威佐夫博弈与贝蒂定理

1、威佐夫博弈威佐夫博弈(Wythoffs game ):有两堆各若干个物品，两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用(ak，bk)( ak ak-1,而bk= ak + k ak-1 + k ak-1 + k - 1 = bk-1 ak-1。所以性质1成立。2。任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势(ak, bk)的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是 非奇异局势。如果使(ak, bk)的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此

2、也是非奇异局势。3。采用适当的方法，可以将非奇异局势变为奇异局势。假设面对的局势是(a,b )，若b = a,则同时从两堆中取走a个物体，就变为了奇异局势(0 ,0 );如果a = ak, b bk那么，取走b - bk个物体，即变为奇异局势；如果a = ak , b ak, b= ak + k则从第一堆中拿走多余的数量a - ak即可;如果a ak ,b= ak + k分两种情况，第一种 明aj (j k)从第二堆里面拿走b - bj即可；第二种，a=bj (j k)从第二堆里面拿走b - aj即可。详细的证明过程：方法一简单分析一下溶易知道两堆石头地位是一样的，我们用余下的石子数(a,b)

3、来表示状态，并画在平面直角坐标系上。 用之前的定理：有限个结点的无回路有向图有唯一的核中所述的方法寻找必败态。先标出(0,0)，然后划去所有(0,k),(k,0),(k,k)的格点；然后找y上方未被划去的格点，标出(1,2),然后划去(1,k),(k,2),(1+k,2 + k)，同时标出对 称点(2,1)，划去(2,k),(1,k),(2 + k,1+k);然后在未被划去的点中在y=x上方再找出(3,5)。按照这样的方法做下 去，如果只列出a = b的必败态的话，前面的一些是(0,0),(1,2),(3,5),(4,7),(6,10),.接下来就是找规律的过程了，可能很辛苦，但是我写得也不容

4、易，而且我暂时没有看到其他地方有这样的证明过程。 忽略(0,0)，记第n组必败态为(an,bn)命题一 ：an + 1二前n组必败态中未出现过的最小正整数分析：如果an+1不是未出现的数中最小的，那么可以从an+1的状态走到一个使an + 1更小的状态，和我们 的寻找方法矛盾。命题二：bn=an + n分析：归纳法：若前k个必败态分别为(ak,ak + k),下证：第k+1个必败态为(ak+1,ak+1 + k+1)从该第k+1个必败态出发，一共可能走向三类状态，从左边堆拿走一些，从右边堆拿走一些，或者从两堆中拿走 一些.下面证明这三类都是胜态.情况一：由命题一，任意一个比ak+1小的数都在之

5、前的必败态中出现过，一旦把左边堆拿少了，我们只要再拿 成那个数相应的必败态即可。情况二(从右边堆拿走不太多)：这使得两堆之间的差变小了，比如拿成了(ak+1,ak+1 + m),则可再拿成 (am,am + m)；情况二(从右边堆拿走很多)：使得右边一堆比左边一堆更少，这时类似于情况一，比如拿成T(ak+1,am)(其 中 amak+1)，则可再拿成(am + m,am)；情况三：比如拿成(am,am + k+1)，则可再拿成(am,am + m).综上所述，任何从(ak+1,ak+1 + k+1)出发走向的状态都可以走回核中.故原命题成立.以上两个命题对于确定(an,bn)是完备的了，给定(

6、0,0)然后按照这两个命题，就可以写出(1,2),(3,5),(4,7),.这样我们得到了这个数列的递推式，以下我们把这两个命题当成是(3间血)的定义。先证明两个性质：性质一：核中的an,bn遍历所有正整数。分析:由命题一，二可得an,bn是递增的，且由an的定义显然。性质二：A=an:n=123,.,B=bn:n = 1,23.，则集合 A,B 不交。分析：由核是内固集，显然。看到这里大家有没有想到Beatty序列呢，实际上an和bn就是一个Beatty序列。an = an,bn=pn,有 an + n=(a+1)n二甲n,解方程 1/(a+1) + 1/a=1得a=(sqrt5+1)/2，

7、到此，我们找到了该必败态的通项公式。实际上这组Beatty序列还有一些别的性质，比如当一个数是Fibonacc i数的时候，另一个数也是Fibonacc i数； 而且两者的比值也越来越接近黄金比，这些性质在得到通项公式之后不难证明。总的来说，这个问题给我们了哪些启示呢？首先用定理所说的方法找核，然后给出核的规律(递推，或是通项)并 且证明。方法二定理0:一个状态是必败态，当且仅当它的所有后继状态都是必胜态；而一个状态是必胜态，只要它的后继状态有 一个以上的必败态即可。证明略去。容易发现下面的定理：定理1 ：(a,b)和(b, a)的胜负性是相同的(a b)。证明：如果(a, b)是必胜态，那么

8、将必胜策略中所有的操作，对第一堆的变为第二堆，对第二堆的变为第一堆，就构成(b, a)的必胜策略定理2 ：若(a, b)是必败态，则对于所有的x a和y b,(x, b)和(a, y)是必胜态。证明：对于x a和y b,不管是哪一种情况，总可以从x堆或y堆中取出一定量的石子使当前状态变为必败态(a, b)，由定理1 , (x, b)和(a, y)为必胜态。对于x a和y 0,(a + d, b + d)是必胜态。证明：与定理2类似。定理4:在所有的必败态中，每个数字恰巧出现一次。证明：有了定理1,对于对称的状态我们只需要处理其中一个，而两个数不会相同(相同的状态必然是必胜态)，于是我 们把每个

9、状态中较小的数字放在前面，每行写一个状态，去掉括号并按照升序排列每行的第一个数，就构成了如下 的矩阵：1 2576 10假设数字1在矩阵中出现两次或两次以上，则有(k,a), (k,b)都为必败态，与定理2矛盾。假设数字10)，则对任意i,必然存在j(0jk)使得 (k-j,k+i-j)或(k,k+i-j)或(k-j,k+i)为必败态(若不如此，则无论如何取石子，对方必胜)，根据假设，显然(k,k+i-j)必 胜，因此，对任意 i,必有(k-j,k+i-j)或(k-j,k+i)=0, (0jk)必败根据鸽巢原理，必然存在3个i的取值(其实是无穷多个，j只有k-1种取值，而i有无数种)记为i1,

10、 i2, i3使得 j1=j2=j3 = mo对这 3 个 i,同样必然存在一对 i，不妨为(i1,i2)使(k-m,k+i1-m)且(k-m,k+i2-m)必败或f(k-m,k+i1) 且f(k-m,k+i2)必败。显然与定理2矛盾，因此不存在这样的数k。观察这个矩阵，我们又可以得到新的定理：定理5:矩阵中每行第一个数恰巧是前面每一行中没有出现过的最小正整数。证明：由定理4，矩阵中每个数字恰巧出现一次，而按照这个矩阵的定义，第二列的数总比同行第一列大，第一列又按照 升序排列，所以每一行的第一个数正好为前面每一行中没有出现过的最小正整数。定理6:矩阵第i行的第二个数正好为第一个数加上i证明：用

11、数学归纳法。对于第一行显然成立若对于前i - 1行均成立，则所有的(ap, ap + p) (ap为第p行第一个数，p = i,因为如果delta = i,我们来说明delta = i。首先，我们考虑从第一堆中取出p个石子，得到状态(ai - p, ai - p + delta)，由定理5，比ai小的数都在 之前出现过，若ai - p出现在某一行的第一列，由于存在必败态(ai - p, ai - p + d) (d delta),故(ai - p, ai - p + delta) 一定为必胜态(定理2);若ai - p出现在某一行的第二列，由于第一列是单增的，因而其对 应的第一列数必小于ai

12、+ delta，故而也可推出其状态为必胜态。对于从两堆石子中取出相同数目的情况与之类似，容易看出一定为必胜态。于是，(ai, ai + delta)状态的胜负性只与状态(ai, ai + d) (d 1，所以对于不同的整数n,【na】各不相同，类似对b有相同 的结果。因此任一个整数至多在集合P或Q中出现一次。*现证明PAQ为空集；(反证法)假设k为PAQ的一个整数，则存在正整数m、n使得【ma】 二【nb】=k。即k ma、nbk+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

13、 + n k+1。 这与m、n为整数有矛盾，所以PAQ为空集。现证明Z+ = PUQ ；已知PUQ是Z+的子集，剩下来只要证明Z+ 是PUQ的子集。(反证法)假设Z+(PUQ)有一个元素k,则存在正整数m、n使得【ma】 k 【(m + 1)a】、【nb】 k 【(n + 1)b】。由此得 ma k 冬【(m + 1)a】 -1(m+1)a -1,类似地有 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

14、 k k+1 0）定理二：如果（a,b）和（c,d）是2个负态，那么a,b,c,d互不相等定理三：（a,b）和（b,a）一定是完全等价的（所以本文中只出现（3, 5）这种状态不出现（5, 3）这种状态（除了本行）定理四：一个状态无法转移到任何一个负态，当且仅当它就是负态。一个状态只要能转移到任何一个负态，那么它就是胜态想清楚了这四点之后，可以开始找出所有负态了。（都是显然的定理，我就不证明了）首先，（3，3）是胜态，（3，4）因为可以转移到（1，2）所以是胜态，（3，5）因为没法转移到任何一个负态， 所以它就是负态。然后，（4，4）是胜态，（4，5）和（4，6）可以转移到（3，5）所以是胜态，

15、（4，7）是负态。现在，有了前3个负态，（1，2）（3，5）（4，7）光凭这3组数据是不可能发现规律的，但是如果结合刚刚找到它们的方法仔细思考，那就不一样了。比如在找第4个负态的时候，我们发现，在（6，6）（6，7）（6，8）（6，9）.这个序列中，如果找到1个负态的话，后面的状态都可以转移到这个状态，所以后面所有的状态都是胜态。（这其 实就是定理二）可是要怎么样知道这个序列里面有没有一个状态不能转移到前面3个负态中的任何1个呢？请注意！如果这个序列中的某个状态不能转移到前面3个负态中的任何1个，那么它就是负态！那么关键来了！状态转移的本质数量关系是什么？本质数量关系就是，如果1个状态的2个数

16、之差等于另外1个状态的2个数之差，那么它们是可以转移的！前面3个状态的2个数之差分别是1，2, 3,那么很明显，上述序列中，有且仅有1个序列是无法转移到这3个序列的，就是那个差为4的状态，即（6, 10）到了这里，可能你已经明白了，如何快速求出所有的负态。负态的2个数之差的序列就是1，2，3，4.如果你认为到了这里，我只是发现规律，只是猜想第i个负态的2个数之差是i，请从头再看一遍。实际上，我们不仅已经得到了一个定理，第i个负态的2个数之差是i我们还得到了另外1个非常重要的定理，第i个负态的较小数是集合A中的最小数，其中A是自然数集，去掉前i-1个负态的2*（i-1）个数，得到的集合。结合定理

17、二可以发现，任何正整数都恰好出现在某个负态中而且仅出现1次！当我想到这个地方的时候，我突然想起来betty贝蒂定理其实我对这个定理印象不深，因为从来没有用过，直到做这个题目才是第一次用。betty定理：对于任意满足1/a+1/b=1,的正无理数a， b，都有结论：a，2a，3a，4a.b，2b，3b，4b.都是不同的数，而且覆盖正整数集。于是我怀疑，betty贝蒂定理和本题有着本质的联系。因为实在是好几年了，所以我想，还是先证明一下betty贝蒂定理，找找感觉吧。betty贝蒂定理的证明：对于任意正整数n，考虑a，2a，3a，4a.里面有多少个数小于n（如果考虑有多少个数小于等于n，那就得不到

18、什么结论，因为根本算不出来，这是由高斯函数的特性决定的）根据高斯函数的特性，kan iff kan即，kn/a （k为整数）因为n/a是无理数，所以上式还等价于k=n/a所以说，a，2a，3a，4a.里面有n/a个数小于 n同理，b，2b，3b，4b.里面有n/b个数小于 n那么，一共有多少呢？这个地方就体现了为什么要是无理数，因为n/a和n/b是无理数，那么就不是整数又因为 n/a+n/b=n，所以n/a+n/b=n-1所以说，对于任意正整数 n，a，2a，3a，4a.b，2b，3b，4b.中有 n-1 个数小于 n由此，可以利用数学归纳法推出betty贝蒂定理。数学归纳法我就不写了，简述如

19、下：考虑a，2a，3a，4a.b，2b，3b，4b.中每个正整数有多少个有1个数小于2，所以有1个1有2个数小于3，所以有1个2有3个数小于4，所以有1个3 就这样，利用第二数学归纳法，可以得到每个正整数都有且仅有1个。证毕口有了贝蒂定理，（1，2）（3, 5）（4, 7）（6，10）。这各序列的通项又要怎么求呢？还是说，这个序列根本没法用贝蒂定理来求？我不是想死套这个定理，只是在思考，这2个东西这么像，应该是有本质联系的吧？如果亲爱的读者是第一次知道贝蒂定理，可能感觉两者的关系并不是很密切。那么你就需要像我初学贝蒂定理的时候一样，找几个简单的实例，比如a=sqrt（2），或者a=sqrt（3

20、）这种简单的例子。a=sqrt（2）时，b=sqrt（2）+2，把正整数集的划分表示成二元组就是： （1,3）（2,6）（4,10）（5,13）（7,17）。差分别是2,4,6,8,10.规律和本题的几乎一样！只不过都乘了 2而已a=sqrt（3）时，b=（sqrt（3）+3）/2，把正整数集的划分表示成二元组就是： （1,2）（3,4）（5,7）（6,9）（8,11）。差分别是1,1,2,3,3.这个貌似没什么规律吧？为什么1个有规律，1个没规律呢？看看a和b的值就一目了然了，a=sqrt(2)时，b=sqrt+2, kb-ka=k*2恒成立。现在是不是感觉这个数列和本题的数列非常像了呢？还不够。不管是a=sqrt(2)还是a=sqrt(3)还是其实的情况，根据贝蒂定理，都可以直接推出：第i二元组中的较小数是集合A中的最小数，其中A是自然数集，去掉前i-1个二元组的2*(i-1