威佐夫博弈


威佐夫博弈

$\rm{Description}$

有两堆,若干个物品,两个人轮流从某一堆或从两堆中取同样多的物品,规定每次最少拿走一个,最多不限制,最后拿光的人获胜。

$\rm{Analysis}$

A表示先手玩家,B表示后手玩家,当前是A进行操作。为了判断 A 是否有必胜策略,可以这样分析:

  • 用有序数对 $(a, b)$ 表示两堆物品的数量状态;
  • $(0, 0)$ 是 $A$ 的必败策略,因为此时 $A$ 已输;
  • 若局面能够移动到 $B$ 无必胜策略的局面,那么这个局面是 $A$ 的必胜态
  • 若局面无论怎么移动,都会变成 $B$ 的必胜太,那么这个局面是 $A$ 的必败态

通过枚举,可以发现 $A$ 的必败态有:

$$
(0, 0),(1, 2),(3, 5),(4, 7),(6, 10),(8, 13),(9, 15),(11, 18),(12, 20)\ldots
$$

用有序数对序列$(a_0, b_0),(a_1, b_1),(a_2, b_2)\ldots$表示上面的必败态,可以看出,满足:$a_0=b_0=0$ 且 $b_i=a_i+i$,$a_i$ 是之前没有出现过的最小自然数。

$\rm{Demonstrate}$

前置命题: $a_{n+1}$ 是前 $n$ 组必败态中没有出现过的最小正整数。

证明命题: $\forall n, b_n=a_n+n$.

考虑归纳证明。若前 $k$ 个必败态分别为 $(a_1, a_1+1), (a_2, a_2+2), \cdots, (a_k, a_k+k)$,下证:第 $k+1$ 个必败态为 $(a_{k+1}, a_{k+1}+k+1)$.

从这个必败态出发,一共可能走向三类状态:从第一堆拿走,从第二堆拿走,或者两堆同时拿走,只需证明这三类都是必胜态。

情况一:从第一堆拿走一些。

因为任意一个比 $a_{k+1}$ 小的数都在之前的必胜态中出现过,第一堆变少之后,只需要把第二堆拿到第一堆对应的必败态。所以对于出现的新的状态,都可以直接指向必败态。

情况二:从第二堆拿走一些。

  1. 拿完之后第二堆仍然大于第一堆。此时可以表示成 $(a_{k+1}, a_{k+1}+m), (m
  2. 拿完之后第二堆小于第一堆,设其拿成了 $(a_{k+1}, m)$,则 $m

情况三:两堆同时拿走一些。

设拿完之后的状态是 $(m, m+k+1)$。因为 $m

所以现在已经得到了数列关系式 $b_n=a_n+n$.

$\rm{Attribute}$

在这个问题中,我们称必败态为奇异局势,记为 $(a_k, b_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}$。整理后,有 $b_k > b_{k-1}>a_{k-1}$,所以不存在自然数被两个奇异局势包含。

2. 任意操作都可以将奇异局势变为非奇异局势

也就是说,必败态的后继一定都是必胜态

对于奇异局势 $(a_k, b_k)$,如果只改变其中一个数,那么由性质$1$,不可能是另一个奇异局势;

如果同时改变两个数,那么这两个数的差不变,由于 $b_k=a_k+k$,对于一个差值,只可能对应一个奇异局势,所以变化后也不可能是另一个奇异局势。

3. 可以将非奇异局势变为奇异局势

根据奇异局势满足 $b_k=a_k+k$,可以分类讨论进行证明。

具体地,对于任意的局势 $(a, b)$,

若 $a=b$,那么同时取走 $a$ 个物品即可变为 $(0, 0)$;

若 $a$ 是一个奇异局势中的 $a_k$,且 $b>b_k$,那么从 $b$ 堆中取出 $b-b_k$个物品,变为 $(a_k, b_k)$.

若 $a$ 是一个奇异局势中的 $a_k$,且 $b

若 $a$ 不属于任何一个奇异局势中,那么 $b$ 一定是一个奇异局势中的 $b_k=a_k+k$,此时有两种情况:

如果 $a>a_k$,从第一堆中拿走多余的 $a-a_k$.

如果 $a

$\rm{Conclusion}$

快速判断局势 $(a, b)$ 是否是奇异局势的方法。

Beatty定理

设 $a, b$ 是正无理数,且 $\frac{1}{a}+\frac{1}{b}=1$,记 $P=\lfloor{na}\rfloor, Q=\lfloor{nb}\rfloor$,$n$ 为任意正整数。

那么 $P\cap Q=\emptyset$ 且 $P\cup Q=N^{*}$.

也就是说:取两个正无理数 $\frac{1}{\alpha}+\frac{1}{\beta}=1$,构造两个数列 $a_n=\lfloor\alpha n\rfloor$ 和 $b_n=\lfloor\beta n\rfloor$,那么两个数列单调递增,并且每个正整数在两个数列当中出现且仅出现一次。

推导

发现奇异局势和 Beatty 定理的条件很像,考虑计算出 $\alpha$ 和 $\beta$.

两个数列 $a_n$ 和 $b_n$ 就是奇异局势中的 $(a_n, b_n)$.

$a_n+n=\lfloor{\alpha\cdot n}\rfloor+n=\lfloor{(\alpha+1)\cdot n}\rfloor=\lfloor{\beta\cdot n}\rfloor$.

所以 $\alpha+1=\beta$

所以 $\frac{1}{\alpha}+\frac{1}{\beta}=\frac{1}{\alpha}+\frac{1}{\alpha+1}=1$.

解得 $\alpha=\frac{\sqrt{5}+1}{2}$.

所以 $a_n=\lfloor\frac{\sqrt{5}+1}{2}n\rfloor$,$b_n=\lfloor(\frac{\sqrt{5}+1}{2}+1)n\rfloor=\lfloor\frac{3+\sqrt{5}}{2}n\rfloor=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

所以根据 Beatty 定理,奇异局势的通项公式为:$a_n=\lfloor(\frac{\sqrt{5}+1}{2})n\rfloor$,$b_n=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

而 $\frac{\sqrt{5}+1}{2}$ 是黄金比,所以威佐夫博弈的奇异局势与黄金比相关。

判断方法

根据奇异局势的性质,对于需要判断的局势 $(a, b), (a

geogebra-export

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
bool eq(double a, double b) {
	if(abs(a - b) < 1e-4) return true;
	else return false;
}
int main() {
	double a, b; cin >> a >> b;
	if(a > b) swap(a, b);
	double t = (1.0 + sqrt(5.0)) / 2.0;
	double k = b - a;
	if(eq(floor(k * t), a) && eq(floor(k * t * t), b)) {
		cout << 0 << endl;
	} else {
		cout << 1 << endl;
	}
	return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇