尼姆数

✍ dations ◷ 2025-09-10 08:26:53 #组合数学,有限域,博弈论,组合博弈论

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

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

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


相关

  • 旅行者腹泻旅行者腹泻(traveler's diarrhea,簡稱TD)是一种肠胃道感染疾病。旅行者腹泻的定义是指在旅途之中,持续排出未成形粪便的状态。常常伴随着腹部痉挛性的疼痛、恶心、发烧、胀气。
  • 麦克斯韦电磁学经典电磁学(英语:Classical electromagnetism)或经典电动力学是理论物理学的分支,通常包含在广义的电磁学,以麦克斯韦方程组和洛伦兹力为基础,主要研究电荷和电流的电磁场及其彼此
  • 酒精性酮症酸中毒酮酸中毒(英语:Ketoacidosis),是一种病理性代谢状态,标志为极高且无法控制的酮症。酮酸中毒的情况下,人体无法足够地控制酮类的产生,导致严重的酮酸堆积使得血液pH极大地降低。在极
  • 德西特威廉·德西特(荷兰语:Willem de Sitter,1872年5月6日-1934年11月20日)是一位荷兰数学家、物理学家和天文学家。德西特生于荷兰弗里斯兰省斯内克。他就读于格罗宁根大学,之后进入格
  • 人工降雨人工降雨或人造雨(英语:rainmaking或cloud seeding),是指在天上有云的情况下,通过人工手段催化降雨。一般是通过降低云层中的温度,使云中小水滴凝聚形成大水滴,从而实现降雨。人工
  • 读者读者可以指:
  • 行刑者刽子手、处刑人或行刑者是古代对于从事直接处决犯人为职业的人的一种称呼。现在世界各国大多以法警或是宪兵作为处决犯人者。汉语中的“刽子手”一词,也可以用来骂人,当作“残
  • 译音音译是一种以原来国家的当地语言读音为依据翻译的形式,一般根据原语言内容的发音在目标语言中寻找发音相近的内容进行替代翻译。音译通常用于姓名、企业、地名和国名等的翻译
  • 内战前时期Antebellum是一个拉丁语单字,意思为战争之前(ante意指“以前”;bellum意指“战争”)。在美国历史及史学史当中,这个单字一般是指美国内战以前,一段地方本位主义逐渐增长的时代,在英
  • 伪基站伪基站,又称假基站、假基地台,是一种利用GSM单向认证缺陷的非法无线电通信设备,主要由主机和笔记本电脑组成,能够搜取以其为中心、一定半径范围内的GSM移动电话信息,并任意冒用他