ニバー

数学において、ナンバはグランディ数とも呼ばれ、組合せゲーム理論で導入され、ゲームNimにおけるヒープの値として定義されます。ナンバは、序数加算と序数乗算を備えた序数であり、序数加算と序数乗算とは異なります。

あらゆる公平なゲームは特定のサイズの Nim ヒープと同等であるとするSprague-Grundy 定理により、公平なゲームのより大きなクラスで Nimbers が発生します。また、 Domineeringのような党派的なゲームでも発生することがあります。

数の加算と乗算は結合的かつ可換的である。各数はそれ自身の加法逆数である。特に、いくつかの順序数のペアについては、それらの数の合計はどちらの加数よりも小さくなる。^[1] 最小排他的演算は数集合に適用される。

ニムは、2 人のプレイヤーが交代で別々の山からオブジェクトを取り除くゲームです。移動は 2 人のプレイヤーのどちらが現在移動しているかではなく位置によってのみ決まり、報酬は対称的であるため、ニムは公平なゲームです。各ターンで、プレイヤーは少なくとも 1 つのオブジェクトを取り除く必要がありますが、同じ山からであれば、任意の数のオブジェクトを取り除くことができます。ゲームの目的は、最後のオブジェクトを取り除くプレイヤーになることです。山のナンバーは、単にその山にあるオブジェクトの数です。ニムの加算を使用して、ゲーム全体のナンバーを計算できます。勝利戦略は、対戦相手のターンでゲームのナンバーを 0 にすることです。^[2]

クラムとは、長方形のボード上でよくプレイされるゲームで、プレイヤーはドミノを水平または垂直に、ドミノが置けなくなるまで順番に並べていきます。最初に動けなくなったプレイヤーが負けます。両プレイヤーの可能な動きは同じなので、公平なゲームであり、数字の値を持つことができます。たとえば、偶数×偶数のボードの数字は 0 になります。偶数×奇数のボードの数字は 0 以外になります。2 × n のボードでは、 nが偶数の場合は数字は 0 になり、 n が奇数の場合は数字は 1 になります。

ノースコットのゲームでは、各プレイヤーのペグが、限られた数のスペースがある列に沿って配置されます。各プレイヤーは、各ターンに列のピースを上下に動かす必要がありますが、他のプレイヤーのピースを越えて動かすことはできません。複雑さを増すために、いくつかの列が積み重ねられています。動かなくなったプレイヤーは負けです。他の多くのニム関連ゲームとは異なり、各列の 2 つのトークン間のスペースの数は、ニムの山のサイズです。対戦相手が 2 つのトークン間のスペースの数を増やした場合は、次の動きでそれを減らします。そうでない場合は、ニムのゲームをプレイし、各列のトークン間のスペースの数のニムの合計が 0 になるようにします。^[3]

ハッケンブッシュは、数学者ジョン・ホートン・コンウェイが考案したゲームです。色付きの線分が端点で互いに接続され、「グラウンド」ラインに接続された任意の構成でプレイできます。プレーヤーは交代で線分を削除します。公平なゲーム バージョン、つまり数字を使用して分析できるゲームは、線から区別を削除して、どちらのプレーヤーも任意の分岐を切断できるようにすることで実現できます。新しく削除された線分に依存してグラウンド ラインに接続している線分も削除されます。このように、グラウンドへの各接続は、数字の値を持つニム ヒープと見なすことができます。さらに、グラウンド ラインへの個別の接続をすべて合計して、ゲーム ステートの数字にすることもできます。

Nimber 加算 (別名nim 加算) は、 nim ヒープのコレクションと同等の単一の nim ヒープのサイズを計算するために使用できます。これは、次のように再帰的に定義されます。 ここで、順序数の集合Sの最小排他数mex( S )は、 Sの要素ではない最小の順序数として定義されます。 $${\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta :\alpha '<\alpha \}\cup \{\alpha \oplus \beta ':\beta '<\beta \}{\bigr )},}$$

有限順序数の場合、対応する数のビットごとの排他的論理和(XOR、⊕で表記)を取ることで、コンピュータ上でnim-sum を簡単に評価できます。たとえば、7 と 14 の nim-sum は、7 を 111、14 を 1110 と書きます。1 の位を足すと 1 になり、2 の位を足すと 2 になり、これを 0 に置き換えます。4 の位を足すと 2 になり、これを 0 に置き換えます。8 の位を足すと 1 になります。したがって、nim-sum は 2 進数では 1001、10 進数では 9 と書きます。

この加法の特性は、mexと XOR の両方が Nim にとって勝利の戦略を生み、そのような戦略は 1 つしか存在し得ないという事実から導かれます。または、直接帰納法で示すこともできます。αとβ を2 つの有限順序数とし、そのうちの 1 つを減算したすべてのペアの nim 和がすでに定義されていると仮定します。αとの XOR がα ⊕ βとなる唯一の数はβであり、その逆もまた同様です。したがって、α ⊕ β は除外されます。 一方、任意の順序数γ < α ⊕ βについて、ξ をα、β、γのすべてとXOR すると、必ずそのうちの 1 つが減算されます ( ξの先頭の 1 は、3 つのうち少なくとも 1 つに存在しなければならないため)。 いずれかが存在する必要がある ため 、γ はいずれかとして含まれ 、したがってα ⊕ β は除外される最小の順序数です。 $${\displaystyle \zeta :=\alpha \oplus \beta \oplus \gamma }$$$${\displaystyle \zeta \oplus \gamma =\alpha \oplus \beta >\gamma ,}$$$${\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma ;\end{aligned}}}$$$${\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}$$

数の加法は結合法則と可換法則を持ち、0は加法の単位元である。さらに、数はそれ自身の加法逆元である。^[4]したがって、α ⊕ β = 0となるのは、 α = βのときのみである 。

ニム乗算（ニム乗算）は再帰的に次のように定義される。

$${\displaystyle \alpha \,\beta =\operatorname {mex} \!{\bigl (}\{\alpha '\beta \oplus \alpha \,\beta '\oplus \alpha '\beta ':\alpha '<\alpha ,\beta '<\beta \}{\bigr )}.}$$

数的乗法は結合法則と可換法則を持ち、序数1は乗法単位元となる。さらに数的乗法は数的加算に対して分配的である。^[4]

したがって、nimbers が集合ではなく適切なクラスを形成するという事実を除けば、nimbers のクラスは環を形成します。実際、それは、非ゼロ順序数αの nimber 乗法逆数が次のように与えられる 、特性2の代数的に閉じた体さえ決定します。

$${\displaystyle \alpha ^{-1}=\operatorname {mex} (S),}$$ ここでSは最小の順序数（数）の集合であり、

1. 0 はSの要素です。
2. 0 < α ′ < αかつβ'がSの要素である場合、もSの要素です。${\displaystyle {\tfrac {1+(\alpha '\oplus \alpha )\beta '}{\alpha '}}}$

すべての自然数nに対して、 2 ^{2 n}未満の数の集合は、位数2 ^{2 n}の ガロア体 GF(2 ^{2 n} )を形成します。したがって、有限数の集合は、n → ∞として、体GF(2 ^{2 n} )の直接極限と同型です。この部分体は代数的に閉じていません。なぜなら、kが 2 のべき乗でない体GF(2 ^k )はこれらの体のいずれにも含まれず、したがって直接極限にも含まれないからです。たとえば、GF(2 ³ )に根を持つ多項式x ³ + x + 1は、有限数の集合には根を持ちません。

数的加算の場合と同様に、有限順序数の数的積を計算する方法があります。これは、次の規則によって決定されます。

1. フェルマーの 2 乗 ( 2 ^{2 n}の形式の数) とそれより小さい数との積は、それらの通常の積に等しくなります。
2. フェルマーの 2 乗xの数平方は、自然数の通常の乗算​​で評価すると3 x /2に等しくなります。

最小の代数的閉体とは、順序数ω ^{ω ω}より小さい数体の集合である。ここでω は最小の無限順序数である。したがって、数体として、ω ^{ω ω は}体上で超越的である。 ^[5]

次の表は、最初の 16 個の数の間の加算と乗算を示しています。

16 は2 ^{2 n}の形式なので、この部分集合は両方の演算で閉じています 。 (単純なテキスト テーブルがお好みの場合は、こちらを参照してください。)

• 超実数