ニバー

数学において、ナンバはグランディ数とも呼ばれ、組合せゲーム理論で導入され、ゲーム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}の形式なので、この部分集合は両方の演算で閉じています 。 (単純なテキスト テーブルがお好みの場合は、こちらを参照してください。)

• 超実数