組合博弈論引入了一類數學對象,稱為尼姆數,它們被定義為尼姆堆的值。但是由於Sprague-Grundy定理,它們可以用於一大類遊戲的研究。事實上,尼姆數是在序數的真類上賦予尼姆加法和尼姆乘法的運算之後形成的概念。這些運算和通常施行於序數類上的加法和乘法並不相同。
基本介紹
- 中文名:尼姆數
- 外文名:nimber
- 套用學科:數學
- 適用領域範圍:組合博弈論
Nimber的特點,加法和乘法表,
Nimber的特點
斯普萊格–格隆第定理指出:每個無偏博弈等價於一個特定大小的尼姆堆。
尼姆數的加法運算(叫做尼姆加法)可以用於計算等價於多個堆的單一尼姆堆大小。這被定義為
。
對於序數的集合S,mex(S)定義為“局外最小序數”,也就是說序數中不是S的元素的最小一個。對於有限序數,尼姆和即是兩個數進行異或運算的結果,這個結果也可以簡單地通過將相加的各個數字的二進制表示逐位進行不進位的加法而得到(例如:100010+110010=10000)。
尼姆數的乘法運算(叫做尼姆乘法)可以遞歸地定義如下:
α β = mex{α′ β + α β′ − α′ β′ : α′ < α, β′ < β} = mex{α′ β + α β′ + α‘ β′ : α′ < α, β′ < β}。
全體尼姆數不能組成普通集合而只是真類。要是把它當作普通集合,或者考慮其任意的一個對尼姆加法和乘法封閉的子集,那么尼姆數的類可以構成一個特徵為2的代數封閉域。尼姆加法的單位元是序數0,而尼姆乘法的單位元則是序數1。由於特徵為2,α的尼姆加法逆元是α自身。非零序數α的尼姆乘法逆元是mex(S),這裡S是滿足以下條件的序數集合:
0是S的元素;
如果0<α ′ < α且β ′是S的元素,那么[1 + (α′ − α) β′ ]/α′也是S的元素。
若n是自然數,小於的尼姆數組成一個階的有限域GF()。
正如尼姆加法,有限序數的尼姆積也有一些有意思的結果:
2的不同費馬冪(形如)的尼姆積等於其序數積;
2的某個費馬冪x的平方根等於3x/2在通常的序數乘法下的結果。
尼姆數組成的最小代數封閉域是由小於的序數構成的,這裡ω是最小的無限序數。因此,作為尼姆數的是尼姆數“域”上最小的超越數。
加法和乘法表
以下表陳列加法和乘法在前16 nimbers之中,因為16是一個費馬冪(即),因此這個子集是封閉的。
Nimber加法:
+ 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
Nimber乘法
× 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