博弈论入门之威佐夫博弈

威佐夫博弈

威佐夫博弈是一类经典的博弈问题

有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利

博弈分析

威佐夫博弈不同于Nim游戏与巴什博奕，它的特殊之处在于不能将两堆石子分开分析。

前辈们在对该博弈游戏做了大量的探索之后最终找到了一些非常有意思的性质

下面的内容不想看的可以跳过直接看结论，其实也没啥乱用233，这部分就是为了拓宽视野的

定义先手必输的局势为奇异局势，前几个奇异局势为(0,0),(1,2),(3,5),(4,7),(6,10) \dots

假设(x,y)为第k个奇异局势

性质：

1. x为前1 \dots k个奇异局势中没有出现过的最小正整数，y=x+k

打表找规律

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

感觉网上证的都不靠谱，那只好让本蒟蒻亲自下手喽

证明这个结论，我们只需要证明两点:(1)任意自然数都出现过(2)任意自然数仅出现一次

对于(1)：反证法，设v这个数没有出现过，那么v可以做一个新的奇异局势的x

对于(2): 反证法

假设数v出现了两次，那么v一定不是所在奇异局势的xx必须之前未出现)

那么v只能同时是两个奇异局势的y，又因为任意一个奇异局势的差值不相同，因此v不可能出现两次

1. 任何操作都会将奇异局势变为非奇异局势

若取走一堆中的石子，那么两对石子的差值会改变，必将成为非奇异局势

若同时取走，因为同一个差值只会对应一种奇异局势，必将成为非奇异局势

1. 可以采取适当的方法将非奇异局势变为奇异局势

显然

结论

人们通过对上述性质的探索，同时结合Betty定理，给出了威佐夫博弈的重要结论

假设两堆石子为(x,y)（其中x<y）

那么先手必败，当且仅当

(y-x)*\frac{(\sqrt{5}+1)}{2}=x

其中的\frac{(\sqrt{5}+1)}{2}实际就是1.618，黄金分割数！怎么样，博弈论是不是很神奇？

代码

题目

#include<cstdio>
#include<algorithm>
#include<cmath>
#define int long long 
using namespace std;
main()
{
    int a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    int temp=abs(a-b);
    int ans=temp*(1.0+sqrt(5.0))/2.0;
    if(ans==a) printf("0");
    else       printf("1");
    return 0;
}