超现实数学习笔记（搬运）

超现实数和不平等博弈。

这种一堆数学推导的东西写了有啥意义……就当自己的笔记吧

1.超实数基础知识

首先定义超实数 surreal number 是什么东西。

$x$ $x_L,x_R$ $\{x_L|x_R\}$ 。

$x_L$ $x_R$ $x_R$ $\le$ $x_L$ 里的元素。（但是我们以后会破坏这条规定……）

~~超实数由两个超实数集构成，禁止套娃~~

$\le$ 定义超实数集上的偏序关系 $\le$ 。

$x\le y$ 当且仅当

\forall d\in x_L,d\not\ge y

且

\forall d\in y_R,d\not\le x

$\le$ 满足自反性：

$\forall x,x\le x$ 。

下面使用（类似）数学归纳法（的东西）证明。

$x=\{|\}$ $x_L=x_R=\varnothing$ $\le$ 的定义）。

下面证明：

\forall d\in x_L,d\not\ge x

\forall d\in x_R,d\not\le x

$\forall d\in x_L$ $d\le d$ $x\le d$ $x_L$ $d$ 自身），得到第一个柿子；

$\forall d\in x_R$ $d\le d$ $d\le x$ $x_R$ $d$ 自身），得到第二个柿子。

$\le$ 的定义）。

$\le$ 具有传递性：

$x\le y,y\le z$ $x\le z$ 。

思路还是（类似）数学归纳法（的东西）。

$x=y=z=\{|\}$ 原命题显然成立。

$\forall d\in x_L,y\le z,z\le d$ $y\le d$ $d\not\ge z$ $y\le d$ $\forall d\in z_R,d\not\le x$ 。

其实还应该满足反对称性：

$x\le y,y\le x$ $x=y$ 。

$=$ $x_L=y_L$ $x_R=y_R$ $=$ ，反对称性会不满足。

$=$ 的……

不同的 $x,y$ $x\le y,y\le x$ 同时满足。很快你会看到一个例子。

$x\le y$ $y\le x$ $\star,\uparrow,\downarrow$ 后这个结论显然不成立，而很多游戏都存在先手必胜局面。

聊了这么多，让我们真正地见识一些超现实数。

$\{|\}$ $0$ $\color{red}1$ ）

$\{0|\}$ $1$ $0\le 1$ $0\not\ge 1$ 。

$\{|0\}$ $-1$ $0\ge -1$ $0\not\le -1$ 。

再进一步：

$\{1|\}$ $2$ $\{|-1\}$ $-2$ 。

$\{0|1\}$ $\frac 1 2$ $\color{red}2$ $\{-1|0\}$ $-\frac 1 2$ 。

容易（？）发现有：

-2\not\ge -1\not\ge-\tfrac 1 2\not\ge 0\not\ge \tfrac 1 2\not\ge 1\not\ge 2

-2\le -1\le-\tfrac 1 2\le 0\le \tfrac 1 2\le 1\le 2

$\{-1|1\}$ $0$ 。

通过这种方式我们能构建实数到超实数的对应关系，称为 达利函数：

\delta(x)=\begin{cases}\{|\}&(x=0)\\\{\delta(x-1)|\}&(x>0,x\in Z)\\\{|\delta(x+1)\}&(x<0,x\in Z)\\\{\delta(\frac{j-1}{2^k})|\delta(\frac{j+1}{2^k})\}&(x=\frac j{2^k},j,k\in Z)\end{cases}

$\frac j{2^k}$ 的实数就靠逼近。

注意，一个超实数不一定有对应的实数。

加法运算 $+$ 。

(x+y)_L=\{\{d+y,d\in x_L\}\cup\{x+d,d\in y_L\}\}

(x+y)_R=\{\{d+y,d\in x_R\}\cup\{x+d,d\in y_R\}\}

$x+y$ 仍是一个超实数，即超实数在加法上封闭。~~我不会证，所以~~略。）

$0$ $0$ $\large\color{red}^{1}$

$0$ $x$ $\{-d,d\in x_R|-d,d\in x_L\}$ $0$ $0$ 。

再举个具体的加法算数栗子。

\tfrac 1 2+\tfrac 1 2=\{\tfrac 1 2|\{\tfrac 1 2,1|2\}\}

$\{\frac 1 2,1|2\}=\frac 3 2$ $\{\frac 1 2|\frac 3 2\}=1$ $\frac 1 2+\frac 1 2=1$ $\frac 1 2$ $\large\color{red}^{2}$

容易（？）发现这个加法满足交换律，结合律。

还有一组结论：

a\le b,c\le d\rightarrow a+c\le b+d

a\ge b,a+b\le c+d\rightarrow c\le d

$\delta(x)+\delta(y)=\delta(x+y),x,y\in R$ ）

2.超实数和不平等博弈

再来讲讲不平等博弈。为了方便把不平等博弈的一个状态描述称为一个棋局。我们称两个玩家为 Alice 和 Bob，当然，先手者可能是 Alice 也可能是 Bob。

举个简单的栗子：改造版 nim 游戏。有好几叠积木，每块积木上写着 A 或 B。Alice 可以进行的操作是，选择一块尚未被移除的写着 A 的积木，移除它和它顶上的所有积木；Bob 相反，可以选定写着 B 的积木。

我们使用两个棋局集合描述一个棋局。（是不是很熟悉？）A 集合是如果当前 Alice 先手，他走一步后可能转移到的所有棋局；B 集合相反。

显然，如果 AB 集合中有一个为空，那么他先手时就显然会无路可走，失败。后手时？不好说。

接下来我们干脆就用一个超实数描述一个棋局。

首先来回顾超实数的加法。一个棋局可能有很多子游戏，玩家操作时可以任选一个子游戏操作。非常显然，超实数的加法就对应两个游戏的合并。

加法逆元就对应一个棋局的反棋局：Alice 和 Bob 的“操作权限”互换。即 Alice 改成选定 B 积木，Bob 改成选定 A 积木。

$x+(-x)=0$ $=$ 有什么含义？

$0$ 棋局显然是一个先手必败的棋局。

任何一个棋局的反棋局与它自身同时进行，也是先手必败，后手的最佳策略就是：在另一半棋局复制对手上一步的行动。

$x\not\le 0,x\ge 0$ $x$ $x\not\ge 0,x\le 0$ $x$ $x=0$ $x\not\le 0,x\not\ge 0$ 表示先手必胜。

好的，回来分析改造版 nim 游戏，先考虑只有一叠积木的情况。

$0$ 。

$\{0|\}=1$ 。

$N$ $\delta(N)$ 。

$N$ $\delta(-N)$ 。

算了直接丢个结论图吧：

多个子游戏直接实数加法即可。

3.超超实数？？？

注意超实数要求右集合的任何一个元素都不小于等于左集合的任意一个元素，然而不符合这个要求的游戏是非常常见的。

比如在刚才的游戏中加入一种同时写着 A 和 B 的积木，显然，单独一块这种积木的游戏对应的“超实数”应该是：

\{0|0\}

$\star$ 。

$\star$ $\star+\star=0$ 。

$\star$ $0$ $\star\not\le 0,\star\not\ge 0$ 。

$\uparrow=\{0|\star\},\downarrow=\{\star|0\}$ $\uparrow$ $\star$ $\downarrow$ $\uparrow=-\downarrow$ 。

$\uparrow$ 小于任何一个正数。你可以把它认为是无穷小一类的东西。

$\star+\uparrow$ $\star+\uparrow+\uparrow$ 又变成 Alice 必胜了。

$\star,\uparrow,\downarrow$ 的情况下判断整个游戏是先手必胜、后手必胜？丢结论：

好力，接下来看例题。

4.例题

P4225

~~可以从题目名称里体会到出题人溢出屏幕的求生欲。~~

$23$ $0,\pm 1,\pm \tfrac 1 2$ $\star,\uparrow,\downarrow$ 。

$\star$ $\star$ $\frac 1 2$ 。

$\sum\uparrow$ $(x+1)^n(x^{-1}+1)^m=x^{-m}(x+1)^{n+m}$ $x^i(i<0)$ 的系数和。很好做。

$\sum \texttt{数字}$ $(x+1)^a(x^{-1}+1)^c(x^2+1)^b(x^{-2}+1)^d=x^{-c-d}(x+1)^{a+c}(x^2+1)^{b+d}$ $x^i(i<0)$ 的系数和。

$(x^2+1)^{b+d}$ $Cx^i$ $(x+1)^{a+c}$ $Cx^j$ $j<-i$ $x^j$ 的系数做一个前缀和即可。

总的来说是道只要懂了不平等博弈就没有难点的题目。

HDU3544

此题问题在于每次操作都会把游戏分成两个游戏相加。

$1\times 1$ $0$ 。

$1\times 2$ $1$ 。

$1\times N$ $\delta(N-1)$ 。

$2\times 1$ $-1$ 。

$2\times 2$ $\{-2|2\}=0$

$2\times 3$ $\{-1|4\}=0$

$2\times 4$ $\{-1,0|6\}=1$

$2\times N$ $\delta(-1+\frac N 2)$

打个究极大表可以发现

$M\times N,2^k\le M<2^{k+1}$ $\delta(-M+2+\frac {N-2}{2^k})$