尼姆数

✍ dations ◷ 2025-04-26 12:35:04 #组合数学,有限域,博弈论,组合博弈论

组合博弈论引入了一类数学对象,称为尼姆数,它们被定义为尼姆堆的值。但是由于斯普莱格–格隆第定理,它们可以用于一大类游戏的研究。事实上,尼姆数是在序数的真类上赋予尼姆加法和尼姆乘法的运算之后形成的概念。这些运算和通常施行于序数类上的加法和乘法并不相同。

斯普莱格–格隆第定理指出:每个无偏博弈等价于一个特定大小的尼姆堆。尼姆数的加法运算(叫做尼姆加法)可以用于计算等价于多个堆的单一尼姆堆大小。这被定义为

对于一个序数的集合 S {\displaystyle S} mex ( S ) {\displaystyle \operatorname {mex} (S)} 定义为“局外最小序数”,也就是说不是 S {\displaystyle S} 的元素的最小一个序数。对于有限序数,尼姆和即是两个数进行异或运算的结果,这个结果也可以简单地通过将相加的各个数字的二进制表示逐位进行不进位的加法而得到(例如,100010+110010=10000)。

尼姆数的乘法运算(尼姆乘法)可以递归地定义如下:

全体尼姆数不能组成普通集合,而只是真类。要是把它当作普通集合,或者考虑其任意的一个对尼姆加法和乘法封闭的子集,那么尼姆数的类可以构成一个特征为2的代数封闭域。尼姆加法的单位元是序数0,而尼姆乘法的单位元则是序数1。由于特征为2, α {\displaystyle \alpha } 的尼姆加法逆元是 α {\displaystyle \alpha } 自身。非零序数 α {\displaystyle \alpha } 的尼姆乘法逆元是 mex ( S ) {\displaystyle \operatorname {mex} (S)} ,这里 S {\displaystyle S} 是满足以下条件的序数集合:

n {\displaystyle n} 是自然数,小于 2 2 n {\displaystyle 2^{2^{n}}} 的尼姆数组成一个 2 2 n {\displaystyle 2^{2^{n}}} 阶的有限域 G F ( 2 2 n ) {\displaystyle GF(2^{2^{n}})}

正如尼姆加法,有限序数的尼姆积也有一些有意思的结果:

尼姆数组成的最小代数封闭域是由小于 ω ω ω {\displaystyle \omega ^{\omega ^{\omega }}} 的序数构成的,这里ω是最小的无限序数。因此,作为尼姆数的 ω ω ω {\displaystyle \omega ^{\omega ^{\omega }}} 是尼姆数“域”上最小的超越数。

以下表格列出了最小16个尼姆数的加法和乘法表。因为16是一个费马幂(形如 2 2 n {\displaystyle 2^{2^{n}}} ),因此这个子集是封闭的。


相关

  • 艾德温·史密斯纸草文稿《艾德温·史密斯纸草文稿》(Edwin Smith Papyrus)是约于公元前1600-1700年间完成的医学论文集:70,也是人类史上第一部关于创伤的外科医学著作,由莎草纸写成,长约5米(因为损毁只剩
  • 尿素循环尿素循环(Urea cycle),也称鸟氨酸循环(Ornithine cycle)是许多哺乳类动物的一个生物化学反应过程,由氨(NH3)生成尿素((NH2)2CO )。尿素循环将高毒性氨转化为尿素排泄。这是人们第一个
  • 二院执政联盟(76)在野党(74)荷兰政府与政治 系列条目国会二院(荷兰语:Tweede Kamer der Staten-Generaal)是荷兰国会的下议院。它拥有150个席位,议员由采用政党名单比例代表制的选举产生
  • 尼罗河三角洲尼罗河干流进入埃及北部后在开罗附近散开汇入地中海,形成了尼罗河三角洲。它以开罗为顶点,西至亚历山大港,东到塞德港(Port Said),海岸线绵延230公里,南北长约160公里,东西宽250公里
  • 行为学动物学人类学 · 人与动物关系学 蜜蜂学 · 节肢动物学 医学节肢动物学 · 鲸类学 贝类学 · 昆虫学 动物行为学 · 蠕虫学 两栖爬行动物学 · 鱼类学 软体动物学 · 哺乳动
  • 囊担子菌纲囊担菌目(Cystobasidiales) 担孢酵母目(Erythrobasidiales) Naohideales囊担菌纲(学名:Cystobasidiomycetes)是担子菌门柄锈菌亚门下的一个纲。该纲包括Cystobasidiales、Erythroba
  • L3微内核L3微内核(英语:L3 microkernel),一种微内核架构的计算机操作系统内核,可以运行在Intel x86架构的电脑上。开发者是约亨·李德克以及他在卡内基梅隆大学(CMU)SET实验室(SET institute
  • 阿部正弘阿部正弘,江户时代末期备后福山藩第7代藩主、阿部家宗家11代。幕末时任老中首座,推动安政改革(日语:安政の改革)。阿部正弘于1819年12月3日(文政2年10月16日)出生在江户的福山藩西
  • 成亮 (顺治进士)成亮,字寅天,号伾岚,直隶大名人。清初政治人物。成亮祖父成基命为明末大学士。父成克巩仕清,亦官至大学士。成亮于顺治六年(1649年)中式己丑科二甲进士,选庶吉士,散馆授编修,官至侍讲
  • 森山直太朗森山直太朗(1976年4月23日-)是一位日本创作型歌手,在东京出生。其母森山良子也是创作型歌手。歌声纯净,被媒体称为“21世纪吟游诗人”。演奏乐器以吉他为主。森山直太朗最著名的