尼姆數
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
組合博弈論引入了一類數學物件,稱為尼姆數,它們被定義為尼姆堆的值。但是由於斯普萊格–格隆第定理,它們可以用於一大類遊戲的研究。事實上,尼姆數是在序數的真類上賦予尼姆加法和尼姆乘法的運算之後形成的概念。這些運算和通常施行於序數類上的加法和乘法並不相同。
尼姆數的特點
斯普萊格–格隆第定理指出:每個無偏博弈等價於一個特定大小的尼姆堆。尼姆數的加法運算(叫做尼姆加法)可以用於計算等價於多個堆的單一尼姆堆大小。這被定義為
對於一個序數的集合,定義為「局外最小序數」,也就是說不是的元素的最小一個序數。對於有限序數,尼姆和即是兩個數進行異或運算的結果,這個結果也可以簡單地通過將相加的各個數字的二進制表示逐位進行不進位的加法而得到(例如,100010+110010=10000)。
尼姆數的乘法運算(尼姆乘法)可以遞歸地定義如下:
全體尼姆數不能組成普通集合,而只是真類。要是把它當作普通集合,或者考慮其任意的一個對尼姆加法和乘法封閉的子集,那麼尼姆數的類可以構成一個特徵為2的代數封閉體。尼姆加法的單位元是序數0,而尼姆乘法的單位元則是序數1。由於特徵為2,的尼姆加法反元素是自身。非零序數的尼姆乘法反元素是,這裏是滿足以下條件的序數集合:
- 0是的元素;
- 如果且是的元素,那麼也是的元素。
若是自然數,小於的尼姆數組成一個階的有限體。
正如尼姆加法,有限序數的尼姆積也有一些有意思的結果:
- 2的不同費馬冪(形如)的尼姆積等於其序數積;
- 2的某個費馬冪的平方等於在通常的序數乘法下的結果。
尼姆數組成的最小代數封閉體是由小於的序數構成的,這裏ω是最小的無限序數。因此,作為尼姆數的是尼姆數「體」上最小的超越數。
加法和乘數表
以下表格列出了最小16個尼姆數的加法和乘數表。因為16是一個費馬冪(形如),因此這個子集是封閉的。
+ | 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 |
× | 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 |
參考文獻
- (英文)Conway, J. H., On Numbers and Games, Academic Press Inc. (London) Ltd., 1976
- (英文) Dierk Schleicher and Michael Stoll, An Introduction to Conway's Games and Numbers, math.CO/0410026 (頁面存檔備份,存於互聯網檔案館) – which discusses games, surreal numbers, and nimbers.
- (中文)談祥伯 譯. 稳操胜券. 上海世紀出版集團 上海教育出版社. 2003年. ISBN 7532092208.
|