威佐夫博弈

chen_zhe · 2019-01-19 21:20:50 · 题解

威佐夫博弈的定义是：

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

那么如果给你这样一个东西，那么如何判断是先手A胜利还是后手B胜利呢？

我们局势为为(a[k],b[k](a[k] \leq b[k],k \in [0,n]))

我们定义一个奇异局势为可以让先手A必输的局势。例如在上面这个题中，可以找到类似于(1,2),(3,5),(4,7)等奇异局势。

由此可得：a[0]=b[0]=0,a[k]是未在前面出现过的最小自然数,而b[k]=a[k]+k。

关于奇异局势，有几个特殊的性质：

• 1、任何自然数都包含在一个，且仅有一个特殊局势中。

• 2、任意操作都可将奇异局势变为非奇异局势。

• 3、通过适当的方法，可以将非奇异局势变为奇异局势。

所谓适当的方法，分为以下几种情况：（假设当前的情况为(a,b)）

• 当a=b的时候，显然可以通过把两堆石子各取走a个，这样就转为了(0,0)，必定为奇异局势。

• 当a=a[k],b>b[k]的时候，取走b-b[k]个石子。

• 当a=a[k],b<b[k]的时候，取走a[k]-ab-a[k]个石子

• 当a>a[k],b=a[k]+k的时候，取走a-a[k]个石子

• 当a<a[k],b=a[k]-k的时候，当a=a[j](j<k)的时候，从第二堆中取走b-b[j]堆，而当a=b[j](j<k)的时候，从第二堆中取走b-a[j]堆即可。

总之：两个人如果都采用正确操作，那么面对非奇异局势，先手必胜；反之，则后手必胜。

如果我给你一个局势(a,b)，如何判断这是不是一个奇异局势呢？有一个很好用的公式如下：

其中 k \in N

由此我们可以得知：若两堆物品个数分别为x,y(x<y)，则k=y-x，再判断x是否等于\lfloor (y-x)\times \dfrac{1+\sqrt{5})}{2} \rfloor即可得知是否是奇异局势。