尼姆数

✍ dations ◷ 2025-04-04 11:21:36 #组合数学,有限域,博弈论,组合博弈论

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

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

对于一个序数的集合 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}}} ),因此这个子集是封闭的。


相关

  • 浣熊浣熊属哺乳纲食肉目浣熊科的一种动物。源自北美洲,因其食前要将食物在水中洗濯,故名浣熊。浣熊通常重5.5到9.5公斤,但有记载的最重的可达28公斤。眼睛周围为黑色,尾有5-6个黑色
  • 丙酰辅酶A羧化酶丙酰辅酶A羧化酶是依赖生物素催化线粒体基质中的丙酰辅酶A羧化反应的酶,该反应的产物是(S)-甲基丙二酰辅酶A。人体表达下列两种丙酰辅酶A羧化酶同工酶:EC 1.1/2/3/4/5/6/7/8/9
  • 甘油酯甘油酯也称为酰基甘油,是甘油和脂肪酸形成的酯类。甘油有三个羟基官能基,可以和一个、二个及三个脂肪酸进行酯化反应,形成的甘油酯分别是单酸甘油酯(英语:Monoglyceride)、二酸甘
  • 二月俄国二月革命(俄语:Февральская революция)是在1917年3月8日(儒略历2月23日)于俄罗斯发生的民主革命,是俄国革命的序幕。为区别于第一次俄国革命,也称第二次俄
  • PCB分板PCB分板,是在大批量电子组装生产工序上的一步重要的工序。为了提高印刷电路板(PCB)制造的产量和表面黏着技术(SMT)产线生产速度,印刷电路板通常被设计成一块大板,在最终产品中使用
  • 画师画师,亦是画家的另一种称呼,多见于中国古代,现代中国画师通常指以绘画为职业的人,包括以绘制大量生产画作(行货画)为生的人,经验和技术较浅的多称为“画工”或“画匠”。本条目的画
  • DDISHTVDDISHTV(蒙古语:ДДэш ТВ)是蒙古国的一家卫星电视运营商,总部位于蒙古国首都乌兰巴托,为“GEM INTERNATIONAL, MCS GROUP”旗下的卫星电视平台。蒙古国地广人稀,故卫星电视成
  • 亚圣奉祀官亚圣奉祀官是一个官名,为孟子嫡系后裔的世袭官称。民国三年,依《崇圣典例》,将孟子后裔73代孟庆棠由原世袭翰林院五经博士,改封奉祀官,民国二十四年改称亚圣奉祀官。
  • 黄薇属黄薇属(学名:)是千屈菜科下的一个属,为落叶灌木植物。该属共有3种,分布于美洲。
  • 卡通卡通为英语Cartoon的音译,是指图画,包含各种非写实风格以及超脱现实的图画艺术,或是故事连环画和四幅一组的漫画。卡通可以分成:政论漫画、滑稽漫画、科学漫画、口袋漫画和连环