Mex（数学）

数学では、整列集合の部分集合の最小値（「除外最小値」）は、集合全体のうちその部分集合に属さない最小の値です。つまり、補集合の最小値です。

集合を超えて、順序付けられたクラスのサブクラスには最小排除値があります。順序数のサブクラスの最小排除値は、組み合わせゲーム理論で公平なゲームにニム値を割り当てるために使用されます。スプレイグ・グランディの定理によると、ゲームの位置のニム値とは、特定の位置から1回の移動で到達できる位置の値のクラスの最小排除値です。^[1]

最小除外値はグラフ理論の貪欲彩色アルゴリズムでも使用されます。これらのアルゴリズムは通常、グラフの頂点の順序を選択し、利用可能な頂点の色の番号を選択します。次に、頂点を順番に検討し、各頂点の色を、その近傍にすでに割り当てられている色のセットの最小除外値になるように選択します。^[2]

以下の例はすべて、与えられた集合が順序数のクラスのサブセットであると仮定しています。 $${\displaystyle {\begin{array}{lcl}\operatorname {mex} (\emptyset )&=&0\\[2pt]\operatorname {mex} (\{1,2,3\})&=&0\\[2pt]\operatorname {mex} (\{0,2,4,6,\ldots \})&=&1\\[2pt]\operatorname {mex} (\{0,1,4,7,12\})&=&2\\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots \})&=&\omega \\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots ,\omega \})&=&\omega +1\end{array}}}$$

ここでωは自然数の 極限順序数です。

スプレイグ・グランディ理論では、最小排除順序数を使用して、通常プレイの公平なゲームのナンバーを決定します。このようなゲームでは、どちらのプレイヤーも各ポジションで同じ動きをし、最後に動いたプレイヤーが勝ちます。最初のプレイヤーがすぐに負けるゲームではナンバーは 0 に等しく、その他のゲームではすべての可能な次のポジションのナンバーの mex に等しくなります。

たとえば、Nimの 1 つの山のバージョンでは、ゲームはn 個の石の山から始まり、移動するプレーヤーは任意の正の数の石を取ることができます。nが 0 個の石の場合、合法的な移動の空のセットの mex が数 0 であるため、数 0 は 0 です。nが 1 個の石の場合、移動するプレーヤーは 0 個の石を残し、 mex({0}) = 1はこの場合の数を与えます。nが 2 個の石の場合、移動するプレーヤーは 0 個または 1 個の石を残すことができ、数 2 は数{0, 1}の mex になります。一般に、 n個 の石の山を持つ移動するプレーヤーは、0 個からn − 1 個の石を残すことができ、数{0, 1, …, n − 1}の mex は常に数nです。 Nim では、石の数がゼロでない場合にのみ最初のプレーヤーが勝ちます。したがって、この分析から、Nim の 1 パイル ゲームで石の開始数がゼロでない場合にのみ最初のプレーヤーが勝ち、勝つ動きはすべての石を取ることであると結論付けることができます。

ゲームを変更して、移動するプレイヤーが最大 3 個の石しか取れないようにすると、n = 4個の石の場合、後続の状態は{1、2、3} の数字を持ち、 mex は 0 になります。4 個の石の数字は 0 なので、最初のプレイヤーが負けます。2 番目のプレイヤーの戦略は、最初のプレイヤーが行う動きに応じて、残りの石を取ることです。n = 5 個の石の場合、 2、3、4個の石の後続の状態の数字は、数字 2、3、0 です (先ほど計算したとおり)。数字の集合{0、2、3}の mex は数字 1 なので、このゲームで 5 個の石から開始すると、最初のプレイヤーが勝ちます。

nimber 値の意味の詳細については、 nimbers を参照してください。