Wythoff博弈
基本的威佐夫博弈（Wythoff Game）描述如下：
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，每次至少取一个，多者不限，最后取光者得胜。
我们使用(a, b)来描述一个局面，可以发现(a, b)和(b, a)其实是一样的，所以在此定义a $ \le $ b。显然(0, 0)是第一个必败态（先手必败局面、奇异局面、P-position），使用P/N-状态或者SG函数可以更容易地分析局面，简单讲就是：“移动可以导致必败态的，此时先手必胜；移动只能导致必胜态的，此时先手必败”。打表可得必败态为(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)、(9, 15)、 $ \cdots $
仔细观察，大胆假设，自行求证，对于 $ (a_n, b_n) $ 有以下性质：
-
$ a_n $ 是前面必败态中未出现过的最小自然数
-
$ b_n = a_n + n $
博弈过程如下：
- 由 $ a_n $ 是未在前面出现过的最小自然数，所以 $ a_n > a_{n-1} $ ，而 $ (b_n = a_n + n) > (a_{n-1} + n) > (a_{n-1} + n - 1 = b_{n-1}) > a_{n-1} $ ，得出任何自然数都包含于有且仅有一个必败态中。
- 当局面处于必败态时，如果只改变其中一个分量，那么与另一个分量就不在同一个必败态中。如果使两个分量同时减少，那么由于a和b的差值不变，改变后也不会是其它的必败态。得出必败态只能转移到必胜态。
- 当局面处于必胜态(x, y)时，如果与x出现在必败态时的另一个分量 $ a_x $ 或者 $ b_x $ 小于y，那么将y取成 $ a_x $ 或者 $ b_x $ ，局面变为必败态 $ (a_x, x) $ 或者 $ (x, b_x) $ ；否则在两堆同时取走 $ x-a_{y-x} $ ，局面变为必败态 $ (a_{y-x}, b_{y-x}) $。得出必胜态可以转移到必败态。
SG函数打表找出规律，就可以开始推导了，实际上 $ a_n $ 和 $ b_n $ 是Betty序列并满足Betty定理，令 $ A = a_{n}, B = a_{n}+n $ 解方程 $ \frac{1}{a} + \frac{1}{a+1} = 1 $ 得 $ a = \frac{\sqrt{5} + 1}{2} $ 。即对于Wythoff博弈局面(a, b)，当 $ a == (int)((b-a) \times \frac{\sqrt{5} + 1}{2}) $ 时先手必败，反之先手必胜。
Betty定理
Betty定理：
如果两个无理数满足 $ \frac{1}{a} + \frac{1}{b} = 1 $，那么对于两个集合 $ A = {[na]}, B = {[na]}, n \in Z $ ，可得出 $ A \cap B = \varnothing, A \cup B = N^{+} $ 。
简单证明如下：
-
$ A \cap B = \varnothing $
由 $ \frac{1}{a} + \frac{1}{b} = 1 $，且a，b为正，可以得到a，b均大于1，所以[na]的跨度大于1，向下取整不会重复。取整数k使得 $ k \in A, k \in B $，那么 $ k < ma < k+1, k < nb < k+1 $ ，化简一下 $ \frac{k}{m} < a < \frac{k+1}{m} \Longrightarrow \frac{m}{k+1} < \frac{1}{a} < \frac{m}{k} $ ，同理 $ \frac{n}{k+1} < \frac{1}{b} < \frac{n}{k} $ ，两式相加 $ \frac{m+n}{k+1} < \frac{1}{a} + \frac{1}{b} < \frac{m+n}{k} \Longrightarrow \frac{m+n}{k+1} < 1 < \frac{m+n}{k} \Longrightarrow k < m + n < k + 1 $ ，与m，n为整数矛盾。
-
$ A \cup B = N^{+} $
取整数k满足 $ k \in C_{N^{+}}A \cup B $ ，此时必有整数m，n满足 $ [ma] < k < [(m+1)a], [nb] < k < [(n+1)b] $ ，化简一下 $ ma < k \le [(m+1)a] - 1 $ ，由于a为无理数，所以有 $ ma < k < (m+1)a - 1 \Longrightarrow \frac{m}{k} < \frac{1}{a} < \frac{m+1}{k+1} $ ，同理 $ \frac{n}{k} < \frac{1}{b} < \frac{m+1}{k+1} $ ，两式相加 $ \frac{m+n}{k} < \frac{1}{a} + \frac{1}{b} < \frac{m+n+2}{k+1} \Longrightarrow \frac{m+n}{k} < 1 < \frac{m+n+2}{k+1} \Longrightarrow m + n < k < k + 1 < m + n + 2 $ ，与m+n和m+n+2间只有一个整数矛盾。