ニム和とニム積の分配法則の証明
ニム和とニム積に関して分配法則が成り立ちます。
『石取りゲームの数学～ゲームと代数の不思議な関係～』(佐藤文広) にある証明とまったく同じです。それを補足しながら説明します。
非負整数全体 ($0$ 以上の整数全体) を $\mathbb{N}_0$ と書きます。
定義 (mex)
非負整数の有限な部分集合 $S \subseteq \mathbb{N}_0$ に対し $\mathrm{mex}(S)$ を $\mathrm{mex}(S) := \min(\mathbb{N}_0 \setminus S)$ と定める。
定義 (ニム和)
$a, b \in \mathbb{N}_0$ に対し $a$ と $b$ のニム和 $a \dot+ b$ を
$a \dot+ b := \mathrm{mex}\{a' \dot+ b, a \dot+ b' \mid 0 \le a' < a, 0 \le b' < b\}$ と定める。
定義 (ニム積)
$a, b \in \mathbb{N}_0$ に対し $a$ と $b$ のニム積 $a \dot\times b$ を
$a \dot\times b := \mathrm{mex}\{a' \dot\times b \dot+ a \dot\times b' \dot+ a' \dot\times b'\mid 0 \le a' < a, 0 \le b' < b \}$ と定める。
簡単のために$\{a' \mid 0 \le a' < a\}$ を $\{a' \}$ と書きます。
例
$\mathrm{mex}\{1, 2, 3\} = 0$
$\mathrm{mex}\{0, 1, 2, \dots, n - 1\} = n$
$\mathrm{mex}\{0, 1, 2, \dots, n - 1, n + 1\} = n$
$2 \dot+ 3 = \mathrm{mex}\{0 \dot+ 3, 1 \dot+ 3, 2 \dot+ 0, 2 \dot+ 1, 2 \dot+ 2\} = \mathrm{mex}\{3, 2,2, 3, 0\} = 1$
$a \dot+ 0 = \mathrm{mex}\{0 \dot+ 0, 1 \dot+ 0, \dots (a - 1) \dot+ 0\} = a$
$a \dot+ b = b \dot+ a$
$a_1 \dot+ b = a_2 \dot+ b \Rightarrow a_1 = a_2$
- 対偶を示す。$a_1 < a_2$ としてよい。$a_2 \dot+ b = \mathrm{mex}\{a_2' \dot+ b, a_2 \dot+ b'\}$ だが $a_2'= a_1$ を考えると $a_1 \dot + b \in \{a_2' \dot+ b, a_2 \dot+ b'\}$ となるから $a_1 \dot+ b \ne a_2 \dot+ b$ である。
$a \dot+ a = 0$
- $a = 0$ の場合成り立つ。上の式が成り立たない最小のものを $b > 0$ とする。$b \dot+ b = \mathrm{mex}\{b' \dot+ b, b \dot+ b'\} \ne 0$ より $b' \dot+ b = 0$ となる $0 \le b' < b$ がある。$b$ の最小性より $b' \dot+ b' = 0$ となり $b = 0$ が導かれて $b > 0$ に矛盾する。
$2 \dot\times 2 = 3$
(理由) 次の4つの mex だから。
$0 \dot\times 2 \dot+ 2 \dot\times 0 \dot+ 0 \dot\times 0 = 0$
$0 \dot\times 2 \dot+ 2 \dot\times 1 \dot+ 0 \dot\times 1 = 2$
$1 \dot\times 2 \dot+ 2 \dot\times 0 \dot+ 1 \dot\times 0 = 2$
$1 \dot\times 2 \dot+ 2 \dot\times 1 \dot+ 1 \dot\times 1 = 1$
$a \dot\times 0 = \mathrm{mex}(\emptyset) = 0$
$a \dot\times 1 = \mathrm{mex}\{a' \dot\times 1 \dot+ 0 \dot+ 0 \mid 0 \le a' < a\} = a$
$a \dot\times b = b \dot\times a$
$\mathrm{mex}$ は minimal excluded number (最小除外数) から来ています。
あとで使うので mex に関する補題を1つ示します。
補題
$S \subseteq T \subseteq \mathbb{N}_0$ かつ $\mathrm{mex}(S) \not\in T$ ならば $\mathrm{mex}(S) = \mathrm{mex}(T)$ である。
証明
$s < \mathrm{mex}(S) \Rightarrow s \in T$ だから $\mathrm{mex}(S) \not\in T$ ならば $\mathrm{mex}(T) = \mathrm{mex}(S)$
(理由?: そのような $s\ (0 \le s < \mathrm{mex}(S))$ は $s \not\in \mathbb{N}_0 \setminus T$ だから $\min(\mathbb{N}_0 \setminus T) \ge \mathrm{mex}(S)$ となり、$\mathrm{mex}(S) \in \mathbb{N}_0 \setminus T$ より等号が成り立つ)
分配法則
$\forall a, b, c \in \mathbb{N}_0$ に対し $(a \dot+ b) \dot\times c = a \dot\times c \dot+ b \dot\times c$
証明
$a', b, c$ などについては分配法則が成り立っているとします (帰納法の仮定)。
以下の式がすべて等しいです。
$(a \dot+ b) \dot\times c$
$\mathrm{mex}\{(a \dot+ b)' \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b)' \dot\times c'\}$
$\mathrm{mex}\{(a' \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c', (a \dot+ b') \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b') \dot\times c'\}$
$\mathrm{mex}\{(a' \dot\times c \dot+ a \dot\times c' \dot+ a' \dot\times c') \dot+ b \dot\times c, a \dot\times c \dot+ (b' \dot\times c \dot+ b \dot\times c' \dot+ b' \dot\times c')\}$
$\mathrm{mex}\{(a \dot\times c)' \dot+ b \dot\times c, a \dot\times c \dot+ (b \dot\times c)'\}$
$a \dot\times c \dot+ b \dot\times c$
[1] = [2] と [5] = [6] はそれぞれニム積、ニム和の定義どおりです。
[3] = [4] は帰納法の仮定と $x \dot+ x = 0$ などを使って整理すると分かります。
[2] = [3] を示しましょう。これができれば [4] = [5] も似たように示せます。[2] の $\mathrm{mex}($ここ$)$ を $S$ として、[3] の $\mathrm{mex}($ここ$)$ を $T$ とします。$S \subseteq T$ です。実際、$(a \dot+ b)' < a \dot+ b = \mathrm{mex}\{a' \dot+ b, a \dot+ b'\}$ だから
$(a \dot+ b)' = a' \dot+ b$
$(a \dot+ b)' = a \dot+ b'$
のどちらかです。よって $S \subseteq T$ です。あとは $((a \dot+ b) \dot\times c =)\ \mathrm{mex}(S) \not\in T$ を示せば上の補題から $\mathrm{mex}(S) = \mathrm{mex}(T)$ となります。つまり [2] = [3] です。
次の2つを示す必要がありますが、ほぼ同じなのでここでは1つ目だけ示します。
$(a \dot+ b) \dot\times c \ne (a' \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c'\ (0 \le a' < a, 0 \le c' < c)$ ★
$(a \dot+ b) \dot\times c \ne (a \dot+ b') \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b') \dot\times c'\ (0 \le b' < b, 0 \le c' < c)$
等号が成り立つと仮定します (背理法)。いま $a' < a$ なので $a \dot+ b \ne a' \dot+ b$ です。
$a \dot+ b > a' \dot+ b$ のとき、$((a \dot+ b) \dot\times c =)\ $ ★の右辺 $\in S$ となり $(a \dot+ b) \dot\times c = \mathrm{mex}(S)$ に矛盾します。($\in$) の部分は $S$ で $(a \dot+ b)' = a' \dot+ b$ の場合を考えると分かります。
$a \dot+ b < a' \dot+ b$ のとき、★ (の $\ne$ を $=$ にしたもの) を
$(a' \dot+ b) \dot\times c = (a \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c'$ ☆
と変形して右辺を整理すれば $(a' \dot+ b) \dot\times c = \mathrm{mex}(S')$ と表したときの $S'$ に☆が現れることが分かり同様に矛盾します。
したがって★は正しいです。★の直後の式も $(a, b') \leftrightarrow (a', b)$ となっているだけなのでたぶん正しいです。よって [2] = [3] が成り立ちます。[4] = [5] も同様にして示せます ([2] = [3] と比べて少し易しいです)。
分配法則のほかに結合法則 $(a \dot\times b) \dot\times c = a \dot\times (b \dot\times c)$ も成り立ちます。
