[ABC229H] Advance or Eat 并不是题解而是超现实数入门

· · 题解

这是一个非对称博弈（partizan game）。与对称博弈的 Grundy 数和 Sprague–Grundy 定理一般，尝试给每个状态赋予一个权值。然而在一般的博弈上很难做！但是，本题中，有一个直觉——每个玩家都倾向于不操作。因此，随着直觉，我们可以定义——

超现实数（surreal number）入门

定义 1. 一个数 x 被递归地定义为一对数的集合 (X_L,X_R)，满足对于任意 x_L\in X_L,x_R\in X_R 有 x_R\le x_L 不成立。

定义 2. 递归地定义一个数 x 为 (X_L,X_R) 小于等于另一个数 y 为 (Y_L,Y_R) 当且仅当对于任何 x_L\in X_L，有 x_L\ge y 不成立，且对于任何 y_R\in Y_R，有 x\ge y_R 不成立，记作 x\le y。

这很符合直觉。某种意义上，x_L 和 x_R 提供了足够确定 x 的信息，因此只需要看 x_L 和 x_R 是否符合我们期待的条件即可。

定义 3. 一个数 x 大于等于 y 当且仅当 y\le x，记作 x\ge y。

定义 4. 一个数 x 等于 y 当且仅当 x\le y 且 y\le x，记作 x=y。

等等？为什么不直接定义为 X_L=Y_L,X_R=Y_R？马上你就会知道——

定义 4. 一个数 x 小于 y 当且仅当 y\le x 不成立且 x\le y，记作 x<y。

定义 5. 一个数 x 大于 y 当且仅当 y<x，记作 x>y。

定义 6. 一个数 x 不小于等于 y 当且仅当 x\le y 不成立，记作 x\nleq y。

定义 7. 一个数 x 不大于等于 y 当且仅当 x\ge y 不成立，记作 x\ngeq y。

等等有什么区别吗？对于数确实没有，但是需要证明一下——而且对于更广义的游戏确实有区别了，这个之后再说。

定义 8. 一个数 x 不等于 y 当且仅当 x=y 不成立，记作 x\neq y。

定义 9. 记 0 为 (\varnothing,\varnothing)，1 为 (\{0\},\varnothing)，-1 为 (\varnothing,0)。

注：为和等于不是一个概念。

定理 1. 0=0,1=1,-1=-1,0<1,-1<0,-1<1。

证明 1. 依定义。

定理 2. 若数 x\le y,y\le z，则 x\le z。

证明 2. 考虑无穷递降法。设 x\le y,y\le z,x\nleq z，x,y,z 分别为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)，如果不成立，则要么 \exists x_L\in X_L,z\le x_L，要么 \exists z_R\in Z_R,z_R\le x，但是我们在第一种情况下有有 y\nleq x_L,y\le z,z\le x_L，第二种情况下有 z_R\nleq y,z_R\le x,x\le y，根据无穷递降法可知不存在这样的 x,y,z。

推论 2.1 若数 x\le y,y\ngeq z，则 x\ngeq z。

推论 2.2 若数 x\le y,y\ngeq z，则 x\ngeq z。

推论 2.3 若数 x\le y,y<z，则 x<z。

推论 2.4 若数 x<y,y\le z，则 x<z。

推论 2.5 若数 x=z,y=w，则 x\le y,x<y,x\ge y,x>y,x\nleq y,x\ngeq y,x=y,x\neq y 分别当且仅当 z\le w,z<w,z\ge w,z\nleq w,z\ngeq w,z=w,z\neq w。

为什么无穷递降法是成立的？因为数就是递归定义的。

定理 3. 对于数 x，有 x\le x。

证明 3. 考虑无穷递降法。设 x 为 (X_L,X_R)。若 x\nleq x，则要么 \exists x_L\in X_L,x_L\ge x，要么 \exists x_R\in X_R,x\ge x_R，在第一种情况下，因为 x_L\in X_L，故根据 \le 的定义，有 x_L\nleq x_L，在第二种情况下，同理有 x_R\nleq x_R。根据无穷递降法可知不存在这样的 x。

推论 3.1 对于数 x 为 (X_L,X_R) 和任意 x_L\in X_L，有 x_L\ngeq x，任意 x_R\in X_R 有 x\ngeq x_R。

推论 3.2 对于数 x，x=x。

定理 4. 对于数 x 为 (X_L,X_R)，有 \forall x_L\in X_L,x_L<x。

证明 4. 考虑无穷递降法。已经证明过 x_L\ngeq x，只需证 x_L\leq x。设 x_L 为 (X_{LL},X_{LR})。若不成立，则要么 \exists x_{LL}\in X_{LL},x_{LL}\ge x，要么 \exists x_{R}\in X_R,x_R\le x_L。后者根据数的定义被保证不可能，而若前者成立，有 x_{LL}\ge x，又因为 x\nleq x_L，有 x_{LL}\nleq x_L。根据无穷递降法可知不存在这样的 x。

定理 5. 对于数 x 为 (X_L,X_R)，有 \forall x_R\in X_R,x<X_R。

证明 5. 考虑无穷递降法。已经证明过 x_R\nleq x，只需证 x_R\geq x。设 x_R 为 (X_{RL},X_{RR})。若不成立，则要么 \exists x_{RR}\in X_{RR},x_{RR}\le x，要么 \exists x_{L}\in X_L,x_R\le x_L。后者根据数的定义被保证不可能，而若前者成立，有 x_{RR}\le x，又因为 x\ngeq x_R，有 x_{RR}\ngeq x_R。根据无穷递降法可知不存在这样的 x。

定理 6. 对于数 x,y，x\le y 或 y\le x。

证明 6. 若 x\nleq y，设 x,y 为 (X_L,X_R),(Y_L,Y_R)，则要么 \exists x_L\in X_L,x_L\ge y，要么 \exists y_R\in Y_R,x\ge y_R，前者说明 y\le x_L\le x，后者说明 y\le y_R\le x。

推论 6.1 对于数 x,y，x<y 当且仅当 x\ngeq y，x>y 当且仅当 x\nleq y。

定义 10. 设数 x,y 为 (X_L,X_R),(Y_L,Y_R)，定义 x+y 为 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})。

很符合直觉的定义。既符合我们对“数”的想象，也符合我们对于“博弈”的想象。但是等等，怎么证明 x+y 一定是一个数？如果不证明是数，怎么利用数的性质？这就需要我们引入——

定义 11. 一个伪数（pseudo-number）/游戏（game） x 被递归地定义为一对伪数的集合 (X_L,X_R)。

定义 12. 递归地定义一个伪数 x 为 (X_L,X_R) 小于等于另一个伪数 y 为 (Y_L,Y_R) 当且仅当对于任何 x_L\in X_L，有 x_L\ge y 不成立，且对于任何 y_R\in Y_R，有 x\ge y_R 不成立，记作 x\le y。

定义 13. 一个伪数 x 大于等于 y 当且仅当 y\le x，记作 x\ge y。

定义 14. 一个伪数 x 等于 y 当且仅当 x\le y 且 y\le x，记作 x=y。

定义 15. 一个伪数 x 小于 y 当且仅当 y\le x 不成立且 x\le y，记作 x<y。

定义 16. 一个伪数 x 大于 y 当且仅当 y<x，记作 x>y。

定义 17. 一个伪数 x 不小于等于 y 当且仅当 x\le y 不成立，记作 x\nleq y。

定义 18. 一个伪数 x 不大于等于 y 当且仅当 x\ge y 不成立，记作 x\ngeq y。

定义 19. 一个伪数 x 不等于 y 当且仅当 x=y 不成立，记作 x\neq y。

定义 20. 一个伪数 x 与 y 无关系当且仅当 x\nleq y 且 y\nleq x，记作 x||y。

是的，伪数就有可能出现没有关系的情况了，比如——

定义 21. 记伪数 \ast 为 (\{0\},\{0\})。

定理 7. \ast || 0。

证明 7. 依定义。

那么伪数有哪些性质呢？实际上，刚才我们大多数证明都没有用到数的 \nexists x_L\in X_L,x_R\in X_R,x_L\ge x_R，因此这些定理可以直接照搬！

定理 8. 若伪数 x\le y,y\le z，则 x\le z。

证明 8. 考虑无穷递降法。设 x\le y,y\le z,x\nleq z，x,y,z 分别为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)，如果不成立，则要么 \exists x_L\in X_L,z\le x_L，要么 \exists z_R\in Z_R,z_R\le x，但是我们在第一种情况下有有 y\nleq x_L,y\le z,z\le x_L，第二种情况下有 z_R\nleq y,z_R\le x,x\le y，根据无穷递降法可知不存在这样的 x,y,z。

推论 8.1 若伪数 x\le y,y\ngeq z，则 x\ngeq z。

推论 8.2 若伪数 x\le y,y\ngeq z，则 x\ngeq z。

推论 8.3 若伪数 x\le y,y<z，则 x<z。

推论 8.4 若伪数 x<y,y\le z，则 x<z。

推论 8.5 若伪数 x=z,y=w，则 x\le y,x<y,x\ge y,x>y,x\nleq y,x\ngeq y,x=y,x\neq y 分别当且仅当 z\le w,z<w,z\ge w,z\nleq w,z\ngeq w,z=w,z\neq w。

定理 9. 对于伪数 x，有 x\le x。

证明 9. 考虑无穷递降法。设 x 为 (X_L,X_R)。若 x\nleq x，则要么 \exists x_L\in X_L,x_L\ge x，要么 \exists x_R\in X_R,x\ge x_R，在第一种情况下，因为 x_L\in X_L，故根据 \le 的定义，有 x_L\nleq x_L，在第二种情况下，同理有 x_R\nleq x_R。根据无穷递降法可知不存在这样的 x。

推论 9.1 对于伪数 x 为 (X_L,X_R) 和任意 x_L\in X_L，有 x_L\ngeq x，任意 x_R\in X_R 有 x\ngeq x_R。

推论 9.2 对于伪数 x，x=x。

准备好进入“加法”的世界了吗？

定理 10. 对于任意伪数 x，x+0 即为 x。

证明 10. 考虑归纳。依定义，设 x 为 (X_L,X_R)，则 x+0 就是 (\{x_L+0|x_L\in X_L\},\{x_R+0|x_R\in X_R\})，根据归纳假设，它就是 (X_L,X_R)，即 x。

这是一个关于为而不是相等的定理！以下两个也是。

定理 11. 对于任意伪数 x,y，x+y 即为 y+x。

证明 11. 考虑归纳。依定义，设 x 为 (X_L,X_R)，y 为 (Y_L,Y_R)，则 x+y 就是 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，y+x 就是 (\{y+x_L|x_L\in X_L\}\cup\{y_L+x|y_L\in Y_L\},\{y+x_R|x_R\in X_R\}\cup\{y_R+x|y_R\in Y_R\})。根据归纳假设，它们是一样的。

定理 12. 对于任意伪数 x,y,z，(x+y)+z 即为 x+(y+z)。

证明 12. 考虑归纳。依定义，设 x 为 (X_L,X_R)，y 为 (Y_L,Y_R)，z 为 (Z_L,Z_R)，则 x+y 就是 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，y+z 就是 (\{y+z_L|z_L\in Z_L\}\cup\{y_L+z|y_L\in Y_L\},\{y+z_R|z_R\in Z_R\}\cup\{y_R+z|y_R\in Y_R\})。因此，(x+y)+z 就是 (\{(x+y)+z_L|z_L\in Z_L\}\cup\{(x+y_L)+z|y_L\in Y_L\}\cup\{(x_L+y)+z|x_L\in X_L\},\{(x+y)+z_R|z_R\in Z_R\}\cup\{(x+y_R)+z|y_R\in Y_R\}\cup\{(x_R+y)+z|x_R\in X_R\})，而 x+(y+z) 就是 (\{x+(y+z_L)|z_L\in Z_L\}\cup\{x+(y_L+z)|y_L\in Y_L\}\cup\{x_L+(y+z)|x_L\in X_L\},\{x+(y+z_R)|z_R\in Z_R\}\cup\{x+(y_R+z)|y_R\in Y_R\}\cup\{x_R+(y+z)|x_R\in X_R\})。根据归纳假设，它们是一样的。

定理 13. 对于任意伪数 x,y,z，x\le y 当且仅当 x+z\le y+z。

证明 13. 考虑归纳。设 x,y,z 为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)。

充分性. 若 x+z\le y+z，则根据加法和 \le 的定义，不存在 x_L\in X_L,x_L+z\ge y+z，也不存在 y_R\in Y_R,x+z\ge y_R+z，根据归纳假设，这等价于不存在 x_L\in X_L,x_L\ge y，也不存在 y_R\in Y_R,x\ge y_R，换言之 x\le y。

必要性. 根据对于任意伪数 w 为 (W_L,W_R)，有 \forall w_L\in W_L,w_L\ngeq w，且 \forall w_R\in W_R,w\ngeq w_R，根据加法的定义，我们有 \forall x_L\in X_L,x_L+z\ngeq x+z，且 \forall z_L\in Z_L,x+z_L\ngeq x+z，且 \forall y_R\in Y_R,y+z\ngeq y_R+z，且 \forall z_R\in Z_R,y+z\ngeq y+z_R，又因为 x\le y，故 \forall x_L\in X_L,x_L+z\ngeq y+z，且 \forall z_L\in Z_L,x+z_L\ngeq y+z，且 \forall y_R\in Y_R,x+z\ngeq y_R+z，且 \forall z_R\in Z_R,x+z\ngeq y+z_R，换言之，x+z\le y+z。

推论 13.1 对于任意伪数 x,y,z，x=y 当且仅当 x+z=y+z。

推论 13.2 对于任意伪数 x,y,z，x<y 当且仅当 x+z<y+z。

推论 13.3 对于任意伪数 x,y,z,w，若 x\le y,z\le w，则 x+z\le y+w。

定理 14. 对于任意数 x,y，x+y 是数。

证明 14. 考虑归纳。设 x,y 为 (X_L,X_R),(Y_L,Y_R)，根据归纳假设，x+y，即为 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，这两个集合里面的元素都是数，因此只需证明前面一个集合里的所有数都小于后面一个集合里的数。而显然有 \forall x_L\in X_L,x_L+y<x+y，\forall y_L\in Y_L,x+y_L<x+y，\forall x_R\in X_R,x+y<x_R+y，\forall y_R\in Y_R,x+y<x+y_R，根据小于的传递性得证。

好的……说了这么多，有什么用呢？我们不是想要一个类似 Grundy 数的东西来着？怎么样把一个游戏化简呢？

定理 15.（化简定理） 设伪数 x 为 (X_L,X_R) 和数 y 为 (Y_L,Y_R) 满足对于任意 x_L\in X_L,x_L\ngeq y，且对于任意 x_R\in X_R,y\ngeq x_R，且不存在 y_L\in Y_L 或 y_R\in Y_R 满足相同的条件，则 x=y。

证明 15.

$x\le y$. 如果不成立，则因为 $\nexists x_L\in X_L,x_L\ge y$，所以 $\exists y_R\in Y_R,x\ge y_R$。但我们又有不等式链 $\forall x_L\in X_L,x_L\ngeq y<y_R$ 且 $\forall x_R\in X_R,y_R\le x\ngeq x_R$，因此 $y_R$ 满足条件。矛盾！故成立。 > 某种意义上，若 $x$ 是数，则 $x$ 就是它的两个集合之间**最简单**，或者说**最先被创造出来的数**。 **定理 16.** $(-1)+1$ 为 $(\{-1\},\{1\})$，它等于 $0$。 **证明 16.** 依化简定理可得。 **定理 17.** 设伪数 $x$ 为 $(X_L,X_R)$，且任取 $Y_L,Y_R$ 满足 $\forall y_L\in Y_L,y_L\ngeq x$ 且 $\forall y_R\in Y_R,x\ngeq y_R$，则 $z$ 为 $(X_L\cup Y_L,X_R\cup Y_R)$ 满足 $z=x$。 **证明 17.** $z\le x$。只需证不存在 $x_L\in X_L,x_L\ge x$，$y_L\in Y_L,y_L\ge x$ 或 $x_R\in X_R,z\ge x_R$。中间的不存在性已经给出，而前者和后者的不存在性由推论 9.1 保证。 $x\le z$。只需证不存在 $x_L\in X_L,x\ge z$，$x_R\in X_R,x_R\ge z$ 或 $y_R\in Y_R,y_R\ge z$。最后一者的不存在性已经给出，而前两者的不存在性由推论 9.1 保证。 **推论 17.1** 设伪数 $x$ 为 $(X_L,X_R)$。若 $X_L$ 存在最大元 $x_L$，则 $x=(\{x_L\},X_R)$。若 $X_R$ 存在最小元 $x_R$，则 $x=(X_L,\{x_R\})$。 **定义 22.** 定义 $M_\alpha$（其中 $\alpha$ 是传统的非负整数！）为所有数 $x$ 为 $(X_L,X_R)$，满足 $X_L\cup X_R\subseteq \bigcup\limits_{\beta<\alpha}M_\beta$。记 $O_\alpha=\bigcup\limits_{\beta<\alpha}M_\beta,N_\alpha=M_\alpha\backslash O_\alpha$。对于 $x\in N_\alpha$，称 $\alpha$ 为 $x$ 的**生日**。 **定理 18.** 若 $O_\alpha$ 是有限集，其元素从小到大为 $x_1,x_2,\cdots,x_n$，则 $N_a=\{(\varnothing,\{x_1\}),(\{x_1\},\{x_2\}),\cdots,(\{x_{n-1}\},\{x_n\}),(\{x_n\},\varnothing)\}$。特别地，$\alpha=0$ 时，有 $N_\alpha=\{0\}$。 **证明 18.** 根据推论 17.1，只需要考虑 $(\{x_i\},\{x_j\})(i<j)$，$(\varnothing,\{x_i\})$ 和 $(\{x_i\},\varnothing)$。显然这些都是数。（除非 $\alpha=0$ 时需要考虑 $\{\varnothing,\varnothing\}$） **必要性.** 如果以上考虑的 $(X_L,X_R)$ 并未在等式右侧列出，则显然存在一个 $x_k$ 满足 $\forall x_L\in X_L,x_L<x_k$ 且 $\forall x_R\in X_R,x_k<x_R$。那么根据化简定理，这个数等于生日最小的一个 $x_k$，并不出现在 $N_\alpha$ 中。 **充分性.** 对于 $(\varnothing,\{x_1\})$，它小于所有 $x_k$。对于 $(\{x_n\},\varnothing)$，它大于所有 $x_k$。对于 $(\{x_i\},\{x_{i+1}\})$，它大于所有 $x_k(k\le i)$ 且小于所有 $x_k(k>i)$。因此，等式右侧的所有数都不出现在 $O_\alpha$ 中，因此出现在 $N_\alpha$ 中。 **推论 18.1** $|N_\alpha|=2^\alpha$。 **定理 19.** 定理 18. 中，对于 $(\varnothing,\{x_1\})$，它等于 $x_1+(-1)$。对于 $(\{x_n\},\varnothing)$，它等于 $x_n+1$。 **证明 19.** 考虑对 $\alpha$ 归纳地逐项验证。设 $\alpha\ge1$。 $(\varnothing,\{x_1\})$. 因为 $x_1$ 是最小的，有 $x_1=(\varnothing,\{x'_1\})$。$x_1+(-1)=(\varnothing,\{x_1\}\cup\{x'_1+(-1)\})=(\varnothing,\{x_1\})$。 $(\{x_n\},\varnothing)$. 因为 $x_n$ 是最大的，有 $x_n=(\varnothing,\{x'_{n'}\})$。$x_n+1=(\varnothing,\{x_n\}\cup\{x'_{n'}+1\})=(\varnothing,\{x_n\})$。 **定义 23.** 定义 $\alpha_+=\max M_\alpha,\alpha_-=\min M_\alpha$。 **定理 20.** 对于任意非负整数 $\alpha,\beta$，有 $\alpha_++\beta_+=(\alpha+\beta)_+,\alpha_-+\beta_-=(\alpha+\beta)_-$。 **证明 20.** 考虑到定理 19. 中有 $(\alpha+1)_+=\alpha_++1$ 和 $(\alpha+1)_-=\alpha_-+(-1)$ 得。 **定理 21.** 定理 18. 中，对于 $(\{x_i\},\{x_{i+1}\})$，它与自己之和等于 $x_i+x_{i+1}$。 **证明 21.** 笔者也不会证，如果读者能够证明欢迎私信笔者交流。 **定理 22.** 设 $\mathbb D=\{\dfrac{p}{2^q}|p\in \Z,q\in \Z_{\ge 0}\}$（其中 $\Z$ 为传统的整数集）。若 $x\in \mathbb D$，设其最简形式为 $x=\dfrac{p}{2^q}(p\in \Z,q\in \Z_{\ge 0})$，递归地定义 $f(x)=\begin{cases}p_+&p\ge 0,q=0\\(-p)_-&p<0,q=0\\(\{f(x-1/2^q)\},\{f(x+1/2^q)\})&q\ge1\end{cases}$，则对于任意 $x,y\in\mathbb D$，有 $f(x+y)=f(x)+f(y)$，$f(x)\le f(y)$ 当且仅当 $x\le y$。 **证明 22.** 由定理 20. 和定理 21. 易得。 > 某种意义上，这给出了一个数的“值”，类似一个对称游戏的 Grundy 数。 **定理 23.** 对于一个生日有限的数 $x$ 为 $(X_L,X_R)$，递归地定义 $g(x)$：设集合 $S=\{\forall x_L\in X_L,y>g(x_L)\land \forall x_R\in X_R,y<g(x_R)|y\in\mathbb D\}$，则： - 若 $\exists y\in \Z,y\in S$，则 $g(x)$ 是绝对值最小的这样的 $y$。 - 否则，$g(x)$ 是 $S$ 中最简形式分母最小的 $y$。 对于任意数 $x,y$，$g(x+y)=g(x)+g(y)$，$g(x)\le g(y)$ 当且仅当 $x\le y$。特别地，$x=y$，当且仅当 $g(x)=g(y)$。 **证明 23.** 由定理 20. 和定理 21. 易得。 **定理 24.** 对于任何 $x\in \mathbb D$，有 $g(f(x))=x$。对于任何生日有限数 $x$，有 $f(g(x))=x$（不是为 $x$）。换言之，$f,g$ 构建了 $\mathbb D$ 和生日有限数（的等价类）的双射，它们互为反函数。 **证明 24.** 由定理 20. 和定理 21. 易得。 > 某种意义上，这确定了一个（超现实）数的“值”，类似一个对称游戏的 Grundy 数。 ## 题解 有了超现实数的前置知识，就可以来做这道题了。 首先，每一列是独立的，我们可以拆开。对于一个状态 $G$，定义 $f(G)=(\{f(G_L)|G_L\in L(G)\},\{f(G_R)|G_R\in R(G)\})$，其中 $L(G)$ 和 $R(G)$ 表示高桥和 Snuke 一步可以走到的状态。那么，把每一列的 $f$ 加起来，如果值 $>0$，高桥胜，值 $<0$，Snuke 胜。值 $=0$ 呢……？实际上是 Snuke 胜，因为高桥是先手。实际上，更一般的，我们有以下定理： **定理 25.** 对于伪数 $x$ 为 $(X_L,X_R)$，定义一个游戏：每次左玩家可以选择 $x_L\in X_L$ 让 $x\gets x_L$，右玩家可以选择 $x_R\in X_R$ 让 $x\gets X_R$，无法操作的人输。那么，左玩家取后手必胜当且仅当 $x\ge 0$，右玩家取后手必胜当且仅当 $x\le 0$。 **证明 25.** 考虑归纳。 **左玩家取后手必胜，若 $x\ge 0$**。这是因为，$\forall x_R\in X_R,x_R\nleq x\ge 0$，因此无论右玩家怎么取都有 $x_R\leq 0$ 不成立，根据归纳假设左玩家必胜。 **左玩家取后手必输，若 $x\ngeq 0$**。这是因为，根据定义，若 $x\ngeq 0$，因为 $0$ 左右集均为空，一定存在 $x_R\in X_R$，满足 $x_R\le 0$，右玩家取这个 $x_R$ 就能必胜。 **右玩家取后手必胜，若 $x\le 0$**。这是因为，$\forall x_L\in X_L,x_L\ngeq x\le 0$，因此无论左玩家怎么取都有 $x_L\geq 0$ 不成立，根据归纳假设右玩家必胜。 **右玩家取后手必输，若 $x\nleq 0$**。这是因为，根据定义，若 $x\nleq 0$，因为 $0$ 左右集均为空，一定存在 $x_L\in X_L$，满足 $x_L\ge 0$，左玩家取这个 $x_L$ 就能必胜。 等等为什么 $f(G)$ 一定是数？还是因为直觉上，每个玩家都倾向于不操作。至于证明我也不会，但是数据范围极小可以在 dp 的时候通过 `assert` 验证这一点。 根据定理 23. 确定 $f$ 的值即可。 ## 更多 实际上关于超现实数还有更多值得讨论的。比如： **A**nd games. 本文着重研究了数的性质，只是在证明时引入了伪数。可以继续研究伪数的性质吗？（实际上 On Numbers And Games 后半部分都在研究这个伪数。） **A**nd games. + **B**ack to impartial. 考虑对称博弈对应的伪数（称为对称伪数）是什么样的。它们满足 $X_L=X_R$，且对于 $X_L$ 中的元素同样如此。……等等，这就是 Grundy 数！$1$ 在里面就是 $\ast$ 呢。 **C**ount to infinity. $X_L$ 和 $X_R$ 可以是无限集吗？（现在不区分 $x$ 和 $f(x)$ 了）$(\{\dfrac14,\dfrac{5}{16},\dfrac{21}{64},\cdots\},\{\dfrac12,\dfrac38,\dfrac{11}{32},\cdots\})$ 是多少？你能刻画出超现实数中哪些数对应了实数吗？$\omega=(\{0,1,2,\cdots\},\varnothing)$ 有什么性质？$\varepsilon=(\varnothing,\{1,\dfrac12,\dfrac14,\cdots\})$ 有什么性质？$\omega\varepsilon=1$ 吗？$(\{0,1,2,\cdots\},\{\omega\})$ 又是什么？$(\{0,1,2,\cdots\},\{\omega,\omega+(-1),\omega+(-2),\cdots\})$ 呢……（实际上，考虑到无限集，每个数的生日是一个**序数**，而每天最大的数对应了这个序数。超现实数加法和序数加法有什么区别？） **A**nd games. + **C**ount to infinity. 步数没有限制，但是一定会结束的游戏看起来很有意思——但是会很难的样子。（毕竟 On Numbers And Games 很多地方也只是在讨论 short games，或者说生日有限的伪数。） **A**nd games. + **B**ack to impartial. + **C**ount to infinity. 诶，好像这又是另一种序数在游戏中的体现……如果说这里的加法代表了数的异或和（Nim 和的话），那序数的异或又怎么算呢。 **D**ifference. 设 $x$ 为 $(X_L,X_R)$，定义 $-x$ 为 $(\{-x_R|x_R\in X_R\},\{-x_L|x_L\in X_L\})$，$x-y$ 为 $x+(-y)$。你能验证关于取相反数和减法的哪些性质呢？ **A**nd games. + **D**ifference. 相反数对于伪数（游戏）也成立嘛！它的博弈意义其实就是交换左玩家和右玩家的合法操作。 **D**ifference. + **E**ven Multiplication...? 既然定义了减法为什么不定义乘法呢？思考一下怎么定义。实际上，答案是若 $x,y$ 为 $(X_L,X_R),(Y_L,Y_R)$，则 $xy$ 定义为 $(\{x_Ly+xy_L-x_Ly_L|x_L\in X_L,y_L\in Y_L\}\cup \{x_Ry+xy_R-x_Ry_R|x_R\in X_R,y_R\in Y_R\}),(\{x_Ly+xy_R-x_Ly_R|x_L\in X_L,y_R\in Y_R\}\cup\{x_Ry+xy_L-x_Ry_L|x_R\in X_R,y_L\in Y_L\})$。很符合我们对于数的想象，但是游戏嘛……没那么符合了。去证明几个关于乘法的定理吧，记得证明 $xy$ 是数呢。 **A**nd games. + **D**ifference. + **E**ven Multiplication...? 这确实不太符合我们对于数的想象。更糟糕的事情是，即使 $x=y$，也有可能 $xz\neq yz$。你能举出一个例子吗？ **A**nd games. + **B**ack to impartial **D**ifference. + **E**ven Multiplication...? 因为对称伪数的相反数还是自己，左集和右集是相同的，所以实际上乘法就是 $(x,y)\to (x,y')+(x',y)+(x',y')$，其中 $x',y'$ 为 $x,y$ 一步可以走到的嘛。等等，这就是 Nim 积！所以对称伪数就是 Nimber！ **A**nd games. + **B**ack to impartial + **C**ount to infinity. + **D**ifference. + **E**ven Multiplication...? 对于序数还能计算 Nim 和与 Nim 积……好震撼！挑战完 $\omega$ 与 $\omega$ 的 Nim 积是 $\omega^2$，来试试看 $\omega$ 与 $\omega^2$ 的 Nim 积是 $2$ 吧。 **C**ount to infinity. + **D**ifference. + **E**ven Multiplication...? + **F**ield. 为什么不试试定义除法呢？等等，生日为 $3$ 的 $3$ 的倒数 $\dfrac13$ 的生日是 $\omega$，这很难办啊……看来必须左右集本身也来一个归纳了。对于 $x>0$，设 $x=(X_L,X_R)$，其中不妨规定 $0\in X_L$ 且 $\forall x_L\in X_L,x_L\ge 0$，设 $X'_L=X_L\backslash \{0\}$。定义 $\dfrac1x$ 为 $y$ 为 $(Y_L,Y_R)$ 为 $$ (\{0\}\cup\{\dfrac{1+(x-x_R)y_L}{x_R}|x_R\in X_R,y_L\in Y_L\}\cup\{\dfrac{1+(x-x_L)y_R}{x_L}|x_L\in X'_L,y_R\in Y_R\},\{\dfrac{1+(x-x_L)y_L}{x_L}|x_L\in X'_L,y_L\in Y_L\}\cup\{\dfrac{1+(x-x_R)y_R}{x_R}|x_R\in X_R,y_R\in Y_R\}) $$ 其中 $\dfrac{p}{q}$ 是 $p$ 与 $\dfrac 1q$ 的乘积。定义中的 $Y_L,Y_R$ 并不是循环定义，而是归纳定义的标志。对于 $x<0$，定义 $\dfrac1x=-\dfrac1{-x}$。去验证 $\dfrac1x$ 是数，且 $\dfrac xx=1$ 吧……于是超现实数形成了域。实际上，它有很多奇妙的性质，比如它是“最大”的有序域…… **A**nd games. + **B**ack to impartial. + **C**ount to infinity. + **D**ifference. + **E**ven Multiplication...? + **F**ield. 序数 Nimber 组成的域有什么好玩的呢？（这在 On Numbers And Games 的第六章讨论。）前几个是域的序数是 $2,4,16,65536,\cdots,\omega^3,\omega^9,\omega^{27},\cdots,\omega^{\omega5},\omega^{\omega25},\omega^{\omega125},\cdots,\omega^{\omega^27},\omega^{\omega^249},\omega^{\omega^2343},\cdots$。最小的代数闭域是 $\omega^{\omega^\omega}$！某种意义上，Nimber 是最简单的域。（在定义里的 $\operatorname{mex}$ 体现了要在合法的情况下尽可能小！）举例来说，如果序数 $\alpha$ 是域但是并非代数闭域，设 $p$ 为 $\alpha$ 中无根的最小（字典序，从高次项比起）多项式，则 $\alpha$ 为 $p$ 的根。 还有更多…… --- 感谢 @[Galois_Field_1048576](https://www.luogu.com.cn/user/360265)、@[ProjectCF](https://www.luogu.com.cn/user/168596) 和 @[zhuzhu2891](https://www.luogu.com.cn/user/515385) 对本文的帮助。（按字典序排序） 参考文献： Donald E. Knuth, Surreal numbers, Addison-Wesley, 1974 John Conway, On Numbers And Games, 1976. 马耀华, 浅谈超现实数与不平等博弈, IOI2021 中国国家候选队论文集, 2021.