尼姆数

✍ dations ◷ 2025-04-02 18:04:28 #组合数学,有限域,博弈论,组合博弈论

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

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

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


相关

  • 分子晶体分子晶体指的是物质内部由范德华力(又称作范德瓦耳斯力或分子间作用力)将分子结合起来的固体物质。晶体的内部由分子构成,大多数非金属单质(少数如Si等除外)、它们的化合物以及大
  • 华南海鲜市场相关争议武汉华南海鲜批发市场,又名华南海鲜市场,是中华人民共和国湖北省武汉市的一个海鲜专业批发市场。位于江汉区汉口金家墩地区,发展大道(二环线)、新华路交界,汉口火车站附近,临近同为
  • 计算机硬件硬件是电脑的物理设备。系统软件存储在硬件内,包含固件(如BIOS)以及操作系统,系统软件使应用软件可以提供用户所需的功能。操作系统通常借由总线与设备沟通,这就需要驱动程序。计
  • 拉珈语支拉珈语是使用于广西壮族自治区金秀瑶族自治县大瑶山地区的一种侗台语族语言,为大部分拉珈人的母语。该语言为一门濒危语言,2000年仅有数千名使用者。拉珈语的系属存在争议,有人
  • 中村事件中村事件是九一八事变前在大兴安岭东侧发生的一次事件。日本一般称之为中村大尉事件或中村大尉杀害事件。1931年(昭和6年)6月27日,出生于日本新潟县蒲原郡(属下越地方)的陆军参谋
  • 章胺章胺(或称章鱼胺,真蛸胺)是一种与去甲肾上腺素相关的内源生物胺,见于多种动物组织中,是某些无脊椎动物的主要神经递质。生物内D-(−)-章胺是由酪胺在多巴胺β-羟化酶催化下羟基化
  • 大阪府第3区大阪府第3区是日本众议院的选区,始于1994年。北海道 13 | 山形县 4 | 静冈县 9 | 岛根县 3 | 大分县 4福井县 3 | 山梨县 3 | 德岛县 3 | 高知县 3 | 佐贺县 3青森县 4 | 岩
  • 二阶段提交二阶段提交(英语:Two-phase Commit)是指在计算机网络以及数据库领域内,为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法。通常,二阶段提交也被
  • 绵悌绵悌(1811年7月23日-1849年12月25日),爱新觉罗氏,清朝乾隆帝皇十七子庆僖亲王永璘第五子。父亲永璘死后,长子庆良郡王绵愍袭封。绵愍死后,奕彩(乾隆帝皇八子仪慎亲王永璇之孙、仪顺
  • 变余结构 (行星天文学)行星科学中的变余结构是指在外太阳系冰卫星上的古老撞击坑地形因为卫星冰外壳的潜变(黏性松弛)或后续的冰火山喷发而消失的状况,因此这种地形又常被称为 "幽灵陨石坑"。而撞击