什么是尼姆数
组合博弈论引入了一类数学对象,称为尼姆数,它们被定义为尼姆游戏尼姆堆的值。但是受于斯普莱格–格隆第定理,它们可以用于一大类游戏的研究。实际上,尼姆数是在序数的真类上赋予尼姆加法和尼姆乘法的运算之后形成的概念。这些运算和一般施行于序数类上的加法和乘法并没有相同。
尼姆数的特点
斯普莱格–格隆第定理表示:每个无偏博弈等价于一个特定大小的尼姆堆。尼姆数的加法运算(叫做尼姆加法)可以用于计算等价于多个堆的单一尼姆堆大小。这被定义为
对于序数的集合S,mex(S)定义为“局外最小序数”,也就是说序数中不是S的元素的最小一个。对于有限序数,尼姆和可以简单地通过将相加的各个数字的二进制表明逐位执行不进位的加法而得到(比如,100010+110010=10000)。
尼姆数的乘法运算(尼姆乘法)可以递归地定义如下:
αβ=mex{α′β+αβ′−α′β′:α′<α,β′<β}=mex{α′β+αβ′+α′β′:α′<α,β′<β}.
全体尼姆数不能构成普通集合而导致真类。若是把它当作普通集合,或者考虑其任意的一个对尼姆加法和乘法封闭的子集,那么尼姆数的类可以组成一个特质为2的代数封闭域。尼姆加法的单位元是序数0,而尼姆乘法的单位元则是序数1。受于特质为2,α的尼姆加法逆元是α本身。非零序数α的尼姆乘法逆元是mex(S),这里S是满足够下条件的序数集合:
0是S的元素;
假使0<α ′<α且β ′是S的元素,那么1+(α′−α)β′/α ′也是S的元素。
若n是自然数,差于的尼姆数构成一个阶的有限域。
正如尼姆加法,有限序数的尼姆积也有一部分故意思的结果:
2的不同费马幂(形如)的尼姆积等于其序数积;
2的某个费马幂x的平方根等于3x/2在一般的序数乘法下的结果。
尼姆数构成的最小代数封闭域是由差于的序数组成的,这里ω是最小的无限序数。所以,作为尼姆数的是尼姆数“域”上最小的超越数。
加法和乘法表
下方表格列出了最小16个尼姆数的加法和乘法表。由于16是一个费马幂(形如),所以这个子集是封闭的。
ption> 尼姆加法 ption>
+ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
1 |
1 |
0 |
3 |
2 |
5 |
4 |
7 |
6 |
9 |
8 |
11 |
10 |
13 |
12 |
15 |
14 |
2 |
2 |
3 |
0 |
1 |
6 |
7 |
4 |
5 |
10 |
11 |
8 |
9 |
14 |
15 |
12 |
13 |
3 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
11 |
10 |
9 |
8 |
15 |
14 |
13 |
12 |
4 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
12 |
13 |
14 |
15 |
8 |
9 |
10 |
11 |
5 |
5 |
4 |
7 |
6 |
1 |
0 |
3 |
2 |
13 |
12 |
15 |
14 |
9 |
8 |
11 |
10 |
6 |
6 |
7 |
4 |
5 |
2 |
3 |
0 |
1 |
14 |
15 |
12 |
13 |
10 |
11 |
8 |
9 |
7 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
8 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
9 |
9 |
8 |
11 |
10 |
13 |
12 |
15 |
14 |
1 |
0 |
3 |
2 |
5 |
4 |
7 |
6 |
10 |
10 |
11 |
8 |
9 |
14 |
15 |
12 |
13 |
2 |
3 |
0 |
1 |
6 |
7 |
4 |
5 |
11 |
11 |
10 |
9 |
8 |
15 |
14 |
13 |
12 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
12 |
12 |
13 |
14 |
15 |
8 |
9 |
10 |
11 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
13 |
13 |
12 |
15 |
14 |
9 |
8 |
11 |
10 |
5 |
4 |
7 |
6 |
1 |
0 |
3 |
2 |
14 |
14 |
15 |
12 |
13 |
10 |
11 |
8 |
9 |
6 |
7 |
4 |
5 |
2 |
3 |
0 |
1 |
15 |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
ption> 尼姆乘法 ption>
× |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
2 |
0 |
2 |
3 |
1 |
8 |
10 |
11 |
9 |
12 |
14 |
15 |
13 |
4 |
6 |
7 |
5 |
3 |
0 |
3 |
1 |
2 |
12 |
15 |
13 |
14 |
4 |
7 |
5 |
6 |
8 |
11 |
9 |
10 |
4 |
0 |
4 |
8 |
12 |
6 |
2 |
14 |
10 |
11 |
15 |
3 |
7 |
13 |
9 |
5 |
1 |
5 |
0 |
5 |
10 |
15 |
2 |
7 |
8 |
13 |
3 |
6 |
9 |
12 |
1 |
4 |
11 |
14 |
6 |
0 |
6 |
11 |
13 |
14 |
8 |
5 |
3 |
7 |
1 |
12 |
10 |
9 |
15 |
2 |
4 |
7 |
0 |
7 |
9 |
14 |
10 |
13 |
3 |
4 |
15 |
8 |
6 |
1 |
5 |
2 |
12 |
11 |
8 |
0 |
8 |
12 |
4 |
11 |
3 |
7 |
15 |
13 |
5 |
1 |
9 |
6 |
14 |
10 |
2 |
9 |
0 |
9 |
14 |
7 |
15 |
6 |
1 |
8 |
5 |
12 |
11 |
2 |
10 |
3 |
4 |
13 |
10 |
0 |
10 |
15 |
5 |
3 |
9 |
12 |
6 |
1 |
11 |
14 |
4 |
2 |
8 |
13 |
7 |
11 |
0 |
11 |
13 |
6 |
7 |
12 |
10 |
1 |
9 |
2 |
4 |
15 |
14 |
5 |
3 |
8 |
12 |
0 |
12 |
4 |
8 |
13 |
1 |
9 |
5 |
6 |
10 |
2 |
14 |
11 |
7 |
15 |
3 |
13 |
0 |
13 |
6 |
11 |
9 |
4 |
15 |
2 |
14 |
3 |
8 |
5 |
7 |
10 |
1 |
12 |
14 |
0 |
14 |
7 |
9 |
5 |
11 |
2 |
12 |
10 |
4 |
13 |
3 |
15 |
1 |
8 |
6 |
15 |
0 |
15 |
5 |
10 |
1 |
14 |
4 |
11 |
2 |
13 |
7 |
8 |
3 |
12 |
6 |
9 |