经 过 数 学 家 的 不 懈 努 力

前言

引子

$$\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\})$$ $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} +&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 0&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 1&1&0&3&2&5&4&7&6&9&8&11&10&13&12&15&14\\\hline 2&2&3&0&1&6&7&4&5&10&11&8&9&14&15&12&13\\\hline 3&3&2&1&0&7&6&5&4&11&10&9&8&15&14&13&12\\\hline 4&4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\\hline 5&5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\\hline 6&6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\\hline 7&7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\\hline 8&8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\\hline 9&9&8&11&10&13&12&15&14&1&0&3&2&5&4&7&6\\\hline 10&10&11&8&9&14&15&12&13&2&3&0&1&6&7&4&5\\\hline 11&11&10&9&8&15&14&13&12&3&2&1&0&7&6&5&4\\\hline 12&12&13&14&15&8&9&10&11&4&5&6&7&0&1&2&3\\\hline 13&13&12&15&14&9&8&11&10&5&4&7&6&1&0&3&2\\\hline 14&14&15&12&13&10&11&8&9&6&7&4&5&2&3&0&1\\\hline 15&15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\\\hline \end{array}$$ $$\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\}$$ $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \times&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 1&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 2&0&2&3&1&8&10&11&9&12&14&15&13&4&6&7&5\\\hline 3&0&3&1&2&12&15&13&14&4&7&5&6&8&11&9&10\\\hline 4&0&4&8&12&6&2&14&10&11&15&3&7&13&9&5&1\\\hline 5&0&5&10&15&2&7&8&13&3&6&9&12&1&4&11&14\\\hline 6&0&6&11&13&14&8&5&3&7&1&12&10&9&15&2&4\\\hline 7&0&7&9&14&10&13&3&4&15&8&6&1&5&2&12&11\\\hline 8&0&8&12&4&11&3&7&15&13&5&1&9&6&14&10&2\\\hline 9&0&9&14&7&15&6&1&8&5&12&11&2&10&3&4&13\\\hline 10&0&10&15&5&3&9&12&6&1&11&14&4&2&8&13&7\\\hline 11&0&11&13&6&7&12&10&1&9&2&4&15&14&5&3&8\\\hline 12&0&12&4&8&13&1&9&5&6&10&2&14&11&7&15&3\\\hline 13&0&13&6&11&9&4&15&2&14&3&8&5&7&10&1&12\\\hline 14&0&14&7&9&5&11&2&12&10&4&13&3&15&1&8&6\\\hline 15&0&15&5&10&1&14&4&11&2&13&7&8&3&12&6&9\\\hline \end{array}$$

加减乘除

$$\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\})$$ $$\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\}$$ $$\alpha+\beta=\operatorname{mex}(\{\alpha+\beta^*|\beta^*\}\cup\{\alpha^*+\beta|\alpha^*\})$$

1. $\alpha+0=\alpha$
2. $\alpha+\beta=\beta+\alpha$
3. $(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)$
4. $\alpha+\alpha=0$

$$\sum_{i=1}^n\alpha_i=\operatorname{mex}\bigcup\limits_{i=1}^n\{\sum_{j=1}^n\begin{cases}\alpha&j=i\\\alpha_j&j\neq i\end{cases}|\alpha<\alpha_j\}$$ $$\alpha\beta=\operatorname{mex}\{\alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*|\alpha^*,\beta^*\}$$

1. $\alpha1=\alpha$
2. $\alpha\beta=\beta\alpha$
3. $(\alpha\beta)\gamma=\alpha(\beta\gamma)$
4. $\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$

$$\prod_{i=1}^n\alpha_i=\operatorname{mex}\{\sum_{I\subsetneq\{1,2,\cdots,n\}}\prod_{j=1}^n\begin{cases}\alpha_j&j\in I\\\beta_j&j\not\in I\end{cases}|\beta_j<\alpha_j\}$$ $$S=\{0\}\cup\{\gamma^{-1}(1+(\alpha+\gamma)\delta)|0<\gamma<\alpha,\delta\in S\}$$

1. 对于任何序数 $\alpha>0$，设 $\beta$ 为 $\alpha^{-1}$ 的一排除项，则 $\alpha\beta\neq 1$。
2. 对于任何序数 $\alpha>0$，设 $\beta$ 为 $\alpha\alpha^{-1}$ 的一（冗余）排除项，$\beta\neq 1$。
3. 对于任何序数 $\alpha>0$，$\alpha\alpha^{-1}=1$。

1. 若 $\beta=0$ 显然，否则设 $\beta=\gamma^{-1}(1+(\alpha+\gamma)\delta)$。则 $1+\alpha\beta=\gamma\gamma^{-1}+\alpha\beta=\gamma^{-1}(\alpha+\gamma+\alpha(\alpha+\gamma)\delta)=\gamma^{-1}(\alpha+\gamma)(1+\alpha\delta)$。显然 $\gamma^{-1}\neq 0$，又因 $\gamma<\alpha$ 有 $\alpha+\gamma$ 不为 $0$，根据归纳假设又有，$1+\alpha\delta$ 不为 $0$，故乘积不为 $0$，即证。
2. 设 $\beta=\gamma\alpha^{-1}+\alpha(\alpha^{-1})^*+\gamma(\alpha^{-1})^*$，其中 $(\alpha^{-1})^*$ 为 $\alpha^{-1}$ 的一排除项。若 $\gamma$ 等于 $0$，这就是前一条所证的。否则因为 $\lambda=\gamma^{-1}(1+(\alpha+\gamma)(\alpha^{-1})^*)$ 也为 $\alpha^{-1}$ 的一排除项，又因为 $\gamma\gamma^{-1}=1$，故 $\beta=1+\gamma(\alpha^{-1}+\lambda)\neq 1$。
3. 显然 $\alpha\alpha^{-1}\neq 0$，因为 $\alpha^{-1}\neq 0$。而由 2 得 $\alpha\alpha^{-1}$ 的排除项不含 $1$，即证。

扩张，扩张，扩张

• $[\Delta\alpha'+\gamma]+\beta$，其中 $\alpha'<\alpha,\gamma<\Delta$。这是因为带余除法。
• $[\Delta\alpha]+\delta$，其中 $\delta<\beta$。

$$\prod_{i=1}^N\alpha_i=\operatorname{mex}\{\sum_{i=0}^{N-1}\sum_{I\subsetneq\{1,2,\cdots,N\},|I|=i}\Delta^i\prod_{j\not\in I}\beta_j|\beta_j<\alpha_j\}$$

1. 先考虑 $\Delta^N$。只需证明它的排除项能取遍所有 $\sum\limits_{i=0}^{N-1}\Delta^i\gamma_i=[\sum\limits_{i=0}^{N-1}\Delta^i\gamma_i]$ 即可。考虑多项式 $q(x)=x^N+\sum\limits_{i=0}^{N-1} x^i\gamma_i$。因为 $<n$ 次多项式均有根，它一定可以因式分解为一次因式。设其根为 $\delta_1,\delta_2,\cdots,\delta_n$，重根算多次。根据 Vieta 定理，$\beta_j=\delta_j$ 即为所求。
2. 再考虑 $\Delta^N\delta$，其中 $\delta\in \Delta$。它的排除项为 $\{\Delta^N\gamma+q(\Delta)(\gamma+\delta)|\gamma<\delta,\deg q<N,[x^i]q(x)\in \Delta\}$。只需证明对于任何 $\gamma$，$q(\Delta)(\gamma+\delta)$ 能取遍每个 $q'(\Delta)$ 即可。因为 $\gamma+\delta\in \Delta$，故其有逆元，而根据归纳假设，次数更小的多项式乘 $\Delta$ 的元素正常乘即可，故取 $q(x)=q'(x)(\gamma+\delta)^{-1}$ 即可。
3. 再考虑 $p'(\Delta),\deg p'=N$。根据归纳假设，次数更小的多项式加法是正常算的，故 $\Delta^N$ 为一个群。因此设 $p'(x)=x^N\delta+q'(x)$，则 $p'(\Delta)=\Delta^N\delta+q'(\Delta)=[\Delta^N\delta]+[q'(\Delta)]=[\Delta^N\delta+q'(\Delta)]=[p'(\Delta)]$。

加法

扩张（试试看！）

1. 对于任何非负整数 $n$，若 $x<[2^n]$，则 $x^2<[2^n]$。
2. 对于任何正整数 $x$，$x$ 与 $x^2$ 的最高位相同。换言之，若 $x<[2^{n+1}]$，则 $x^2+x<[2^n]$。
3. 对于任何非负整数 $n$，$\{x^2+x|x<[2^{2^n}]\}=[2^{2^n-1}]$
4. 对于任何非负整数 $n$，$[2^{2^n}]^2=[\dfrac32\times2^{2^n}]$。

1. 因为 $(x+y)^2=x^2+y^2$，且 $[2^n]$ 是一个群，因此只需证明 $x=[2^k]$ 的情况 $x^2<[2^{k+1}]$ 即可。设 $k=\sum [2^{a_i}]$，则 $x=\prod [2^{2^{a_i}}]$。（因为 $[2^{2^{a_i}}]$ 对四则运算封闭，所以乘法和直接乘没区别）因此 $x^2=\prod [2^{2^{a_i}}]^2$。依归纳假设，这即为 $x^2=\prod [2^{2^{a_i}}]+[2^{2^{a_i}-1}]$。按照乘法分配律展开后，每一项的[普通]积都不超过 $[2^{k}]$，因此 Nim 积也不超过 $[2^k]$（因为 Nim 积的排除项个数为普通积），即小于 $[2^{k+1}]$，故和小于 $[2^{k+1}]$。
2. 根据 1.，有 $y\to y^2$ 是 $[2^n]$ 到 $[2^n]$ 的双射，同时也是 $[2^{n+1}]$ 到 $[2^{n+1}]$ 的双射，因此是 $[2^{n+1}]\backslash [2^n]$ 到自身的双射，即证。自然推出后半句。
3. 之前证明过前者的大小刚好为 $[2^{2^n-1}]$，而取值范围也在 $[2^{2^n-1}]$ 内，即证。
4. 根据 3.，最小需要扩展的多项式为 $p(x)=x^2+x+[2^{2^n-1}]$，即 $[2^{2^n}]^2=[2^{2^n}]+[2^{2^n-1}]=[2^{2^n}+2^{2^n-1}]=[\dfrac 32\times2^{2^n}]$。

计算

关于本题