分配ニムについて
この記事は 競技科学people 1st Advent Calendar 2025 の10日目の記事です。
はじめに
はじめまして、ミカン小僧と申します。今回は、僕が今まで細々と続けてきた研究（？）について話したいと思います。
「数学の研究」というと、大学で習うような難しい数学をやったり、未解決問題を解決したりするようなことを想像する人が多いと思いますが、僕は凡人なのでそんな大したことをしているわけではありません。ですから、肩ひじ張らずにゆる〜い気持ちで読んでいただけると幸いです。
さて、タイトルにある通り、この記事で話すのは「ニム」というゲームについてです。この記事では、まずニムについて説明し、その後今回扱う「分配ニム」について話したいと思います。ニムについてもう知っているという方は、ニムの章を飛ばして読んでいただいても構いません。
第一章 ニム
まず、ニムのルールを説明します。
いくつかの石からなる山が複数個あり、先手と後手に分かれたプレイヤーは以下の操作を行う。
操作:1つの山を選び、その山から1個以上の石をとる。
双方がこの操作を繰り返し、先に操作を行えなくなったほうが負け。
山が$n$個あるときのニムの局面を、次のように表すことにします。
$\left( a_{1}, a_{2}, ⋯ , a_{n} \right)$
ここで、$a_{b}\left( 1\leqq b \leqq n \right) $は非負整数であるとします。
では、どのような局面のとき、どちらが必勝法を持つのでしょうか？
このことを考えるために、$\mathcal{P}$局面と$\mathcal{N}$局面について説明します。
先手必勝の局面を$\mathcal{P}$局面、
後手必勝の局面を$\mathcal{N}$局面という。
順々に考えていきましょう。まず、終了局面（何も操作を行えない局面）は、先手が何も操作を行えないため$\mathcal{P}$局面ですね。次に、一手で終了局面に遷移できる局面はすべて$\mathcal{N}$局面になります。先手が操作して終了局面にすれば、後手は何も操作を行えないからです。
同様に帰納的に考えていくと、次の命題を得ます。
局面の集合$P$、$N$があり、$T$を終了局面の集合とするとき、$P$、$N$が次の条件を満たせば、$P$は$\mathcal{P}$局面、$N$は$\mathcal{N}$局面の集合とそれぞれ一致する。
- $T \subset P$
- $G \in N$のとき、$G' \in P$をみたし局面$G$から一手で遷移できる局面$G'$が存在する。
- $G \in P$のとき、$G' \in P$をみたし局面$G$から一手で遷移できる局面$G'$は存在しない。
これで準備は終わりました。実際に、ニムについて考えていきましょう。まずは山の数が$1$個の場合です。
$n=1$のとき
$\left( 0 \right)$のとき、終了局面なので$\mathcal{P}$局面。石の数が$0$より大きいとき、先手が山の石をすべて取ることで終了局面に遷移できるので、$\mathcal{N}$局面となります。
$n=2$のとき
上の結果より、$\left( 0, 0 \right)$のとき$\mathcal{P}$局面、$\left( 0, n \right)$または$\left( n, 0 \right)$$\left( n \gt 0 \right)$のとき$\mathcal{N}$局面ですね。石の数がどちらも$1$以上の時について考えてみましょう。$\left( 1, 1 \right)$のとき、一手で遷移できる局面は$\left( 0, 1 \right)$または$\left( 1, 0 \right)$です。これらはどちらも$\mathcal{N}$局面ですから、$\left( 1, 1 \right)$は$\mathcal{P}$局面です。
したがって$\left( 1, n \right)$または$\left( n, 1 \right)$$\left( n \gt 1 \right)$のとき$\mathcal{N}$局面となることも分かります。
以下続けていくと、次の結果が得られます。
局面を$\left( a_{1}, a_{2} \right)$とすると、
$a_{1} = a_{2}$のとき$\mathcal{P}$局面
$a_{1} \neq a_{2}$のとき$\mathcal{N}$局面
証明
二つの山の石の個数に関する帰納法で証明する。まず$a_{1}+a_{2}=0$、すなわち$a_{1}=a_{2}=0$のとき、これは終了局面であるから$\mathcal{P}$局面である。次に$a_{1}+a_{2}=k \gt 0$で主張が成り立つと仮定し、$a_{1}+a_{2}=k+1$のときを考える。$a_{1}=a_{2}$のとき、一手後の局面としてありうるのは$\left( a'_{1}, a_{2} \right)$または$\left( a_{1}, a'_{2} \right)$だが、$\left( a'_{1}, a_{2} \right)$のとき$a'_{1}+a_{2}\leq k$かつ$a'_{1} \lt a_{2}$が成り立つので、仮定よりこれは$\mathcal{N}$局面。同様に$\left( a_{1}, a'_{2} \right)$も$\mathcal{N}$局面であるから、命題1より$\left( a_{1}, a_{2} \right)$は$\mathcal{P}$局面。$a_{1} \gt a_{2}$のとき、山$1$から$a_{1}-a_{2}$個の石を取ることで、局面$\left( a_{2}, a_{2} \right)$に遷移できる。これは仮定より$\mathcal{P}$局面であるから、命題1より$\left( a_{1}, a_{2} \right)$は$\mathcal{N}$局面。$a_{1} \lt a_{2}$のときも同様に考えることで、$a_{1} \neq a_{2}$のとき$\mathcal{N}$局面であると分かる。(証明終)
$n \geq 3$のとき
山が三つの時、どの山にも石の数が$1$個以上ある$\mathcal{P}$局面を列挙してみると、次のようになります。
| (1,2,3) | (1,4,5) | (1,6,7) | (1,8,9) |
| (2,4,6) | (2,5,7) | (2,8,10) | (2,9,11) |
| (3,4,7) | (3,5,6) | (3,8,11) | (3,9,10) |
・・・
法則がありそうにも見えますが、よく分からないですね。とりあえず、石の数の和は必ず偶数になりそうです。
さて、ここで新たな概念を導入します。ニム和です。これは排他的論理和ともいわれ、次のように定義される演算です。
非負整数$a,b$を二進法で繰り上がりなしに足し合わせた値を$a,b$のニム和といい、$a\oplus b$と表す。
$2\oplus 3=10_{(2)}\oplus 11_{(2)}=01_{(2)}=1$
一桁目は、$0+1=1$なので$1$
二桁目は、$1+1=2=10_{(2)}$となりますが、繰り上がりは無視されるので$0$のみが残ります。
ニム和は次を満たします。
$a\oplus b =b\oplus a$(交換法則)
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$(結合法則)
$a\oplus 0=a$
$a\oplus a=0$
実は、ニム和を使うことで、$\mathcal{P}$局面と$\mathcal{N}$局面を見分けることが出来るようになります。なんと、次の定理が成り立つのです！
あるニムの局面を$G(a_{1},a_{2},a_{3}, \cdots ,a_{n})$とする。このとき、
$a_{1}\oplus a_{2}\oplus a_{3}\oplus\cdots\oplus a_{n}=0$ ならば$G$は$\mathcal{P}$局面
$a_{1}\oplus a_{2}\oplus a_{3}\oplus\cdots\oplus a_{n}\neq 0$ ならば$G$は$\mathcal{N}$局面
証明
終了局面$(0,0,0,\cdots ,0)$のニム和は$0$。$a_{1}\oplus a_{2}\oplus a_{3}\oplus\cdots\oplus a_{n}=0$のとき、$a_{k}(1\leq k\leq n)$を$a'_{k}$にする操作をすると、
$a_{1}\oplus a_{2}\oplus \cdots \oplus a'_{k}\oplus \cdots \oplus a_{n}=(a_{1}\oplus a_{2}\oplus \cdots \oplus a_{k}\oplus \cdots \oplus a_{n}) \oplus a_{k} \oplus a'_{k}=a_{k} \oplus a'_{k}\neq 0$
したがって、ニム和が$0$の局面からニム和が$0$の局面に遷移することはできない。
$a_{1}\oplus a_{2}\oplus a_{3}\oplus\cdots\oplus a_{n}=b(b\neq 0)$のとき、$b$の最上位の桁の値が$1$となるような$a_{k}(1\leq k\leq n)$をとると、$a_{k}\oplus b \lt a_{k}$であり、$a_{1}\oplus a_{2}\oplus \cdots \oplus a_{k}\oplus b\oplus \cdots \oplus a_{n}=b\oplus b=0$であるから、$a_{k}$を$a_{k} \oplus b$にする操作を行うことでニム和が$0$の局面に遷移することが出来る。
以上より、命題$1$からニム和が$0$となる局面は$\mathcal{P}$局面、そうでない局面は$\mathcal{N}$局面。(証明終)
第二章 分配ニム
ようやく本題です。次のような問題を考えます。
$N$君と$P$君が次のようなゲームを行っています。
$0$個以上の石が置かれた山が$3$個ある。$2$人のプレイヤーは、交互に次のいずれかの操作を行う。
- 山を$1$つ選び、そこから$1$個以上の石を取る。
- $3$つの山の石の数がすべて$0$より大きいとき、山を$1$つ選び、その山に含まれるすべての石を、残りの$2$つの山に配分する。配分する割合は自由に決めてよい。
先に操作ができなくなったほうが負け。
$N$君が先攻、$P$君が後攻です。石の初期配置$(a, b, c)$が入力されるので、$N$君が必勝戦略を持つ時はN、$P$君が必勝戦略を持つ時はPと出力してください。ただし、$1\leq a\leq b\leq c\leq 10^6$です。
$(1,2,3) \rightarrow (3,0,3) \rightarrow (3,0,1)\rightarrow (1,0,1)\rightarrow (1,0,0)\rightarrow (0,0,0)$
このとき、先手の勝利となります。
$\mathcal{P}$局面かどうか小さいほうから求めて確かめるという方針を取ると、計算量は$\mathcal{O}(N^3)$となり、制約より時間内に間に合いません。したがって、$\mathcal{P}$局面と$\mathcal{N}$局面を素早く見分ける方法を見つけなければならないようです。
まず、$a=0$のときについて考えてみます。条件より、操作２を行うことが出来ないので、通常のニムと同じ、すなわち$b=c$のとき$\mathcal{P}$局面、$b\neq c$のとき$\mathcal{N}$局面だと分かります。
$a\gt 0$のときはどうでしょうか。操作２が特殊なので、これについて考えてみましょう。
まず、操作２を行うと、$1$個以上石がある山が$3$個から$2$個に減ることが分かると思います。すると、もう操作２は行えなくなるので、通常のニムと同じルールになります。また、操作２を行う前と後で石の総数は変わらないので、次のことが分かります。
$a+b+c$が偶数ならば、局面$(a,b,c)$は$\mathcal{N}$局面。
証明
$a+b+c$が偶数のとき、操作２を行うことで、局面$(\frac{a+b+c}{2},\frac{a+b+c}{2},0)$に遷移することが出来る。これは$\mathcal{P}$局面であるから、命題１より局面$(a,b,c)$は$\mathcal{N}$局面
よって$a+b+c$が奇数かつ$0\lt a\lt b\lt c$を満たす$(a,b,c)$について考えればよいことになります。以後、このような局面を非自明な局面と呼ぶことにします。では、$c\lt32$を満たす非自明な$\mathcal{P}$局面を全列挙してみましょう。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| (1, 2, 4) | (2, 3, 6) | (3, 4, 8) | (4, 5, 6) | (5, 7, 13) | (6, 7, 14) | (8, 9, 14) | |
| (1, 3, 5) | (2, 5, 8) | (3, 7, 11) | (4, 7, 12) | (5, 9, 11 ) | (6, 10, 11) | (8, 10, 13) | |
| (1, 6, 8) | (2, 7, 10) | (3, 9, 13) | (4, 9, 10) | (5, 12, 14) | (6, 12, 13) | (8, 11, 12) | |
| (1, 7, 9) | (2, 9, 12) | (3, 10, 14) | (4, 13, 14) | ||||
| (1, 10, 12) | (2, 11, 14) | ||||||
| (1, 11, 13) |
これらから法則を類推するのは難しそうですね。普通のニムではニム和が効果的だったので、このニムでもニム和を試してみましょう。上の表にある局面についてそのニム和を計算したものは、以下の通りになります。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 7 | 7 | 15 | 7 | 15 | 15 | 15 | |
| 7 | 15 | 15 | 15 | 7 | 7 | 15 | |
| 15 | 15 | 7 | 7 | 7 | 7 | 15 | |
| 15 | 7 | 7 | 7 | ||||
| 7 | 7 | ||||||
| 7 |
この結果から、次の予想が立てられます。
$a\oplus b\oplus c=2^n-1$を満たすような正整数$n$が存在するとき、局面$(a,b,c)$は$\mathcal{P}$局面。
しかし、簡単に反例が見つかるので($(1,4,6)$など)この予想は否定されます。さらに条件が必要なようです。確認するために、実際に二進法で表してみましょう。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| (1, 10, 100) | (10, 11, 110) | (11, 100, 1000) | (100, 101, 110) | (101, 111, 1101) | (110, 111, 1110) | (1000, 1001, 1110) | |
| (1, 11, 101) | (10, 101, 1000) | (11, 111, 1011) | (100, 111, 1100) | (101, 1001, 1011) | (110, 1010, 1011) | (1000, 1010, 1101) | |
| (1, 110, 1000) | (10, 111, 1010) | (11, 1001, 1101) | (100, 1001, 1010) | (101, 1100, 1110) | (110, 1100, 1101) | (1000, 1011, 1100) | |
| (1, 111, 1001) | (10, 1001, 1100) | (11, 1010, 1110) | (100, 1101, 1110) | ||||
| (1, 1010, 1100) | (10, 1011, 1110) | ||||||
| (1, 1011, 1101) |
この表をじっと観察していると、次の予想を立てることが出来ます。
局面$(a,b,c)$が$\mathcal{P}$局面であるとき、次が成り立つ。
- $a\oplus b\oplus c=2^n-1$をみたす正整数$n$が存在する。
- $a,b,c$を$2^n$で割った余りを$a',b',c'(0\leq a',b',c'\lt 2^n)$とするとき、$a',b',c'$は互いに相異なる正整数である。
- $a,b,c$を$2^{n-1}$で割った余りを$a'',b'',c''(0\leq a'',b'',c''\lt 2^{n-1})$とするとき、$a'',b'',c''$の中に$0$が存在するまたは互いに等しい$2$数の組が存在する。
実際に、この条件を満たす局面$(a,b,c)$を列挙すると、次のようになります。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| (1, 2, 4) | (2, 3, 6) | (3, 4, 8) | (4, 5, 6) | (5, 7, 13) | (6, 7, 14) | (8, 9, 14) | |
| (1, 3, 5) | (2, 5, 8) | (3, 7, 11) | (4, 7, 12) | (5, 9, 11) | (6, 10, 11) | (8, 10, 13) | |
| (1, 6, 8) | (2, 7, 10) | (3, 9, 13) | (4, 9, 10) | (5, 12, 14) | (6, 12, 13) | (8, 11, 12) | |
| (1, 7, 9) | (2, 9, 12) | (3, 10, 14) | (4, 13, 14) | ||||
| (1, 10, 12) | (2, 11, 14) | ||||||
| (1, 11, 13) |
この予想は成り立ちそうですね。実際に証明してみましょう。
第三章 分配ニムの必勝法
以下、予想を満たす局面のことを純粋な局面と呼び、局面のニム和の$2^k$の位の数を$f(k)$、ある数$i$の$2^k$の位の数を$g_{i}(k)$とします。
まず、純粋な局面から純粋な局面に遷移することが出来ないことを示しましょう。この局面を$G(a,b,c)$とすると、$G$のニム和と遷移後の局面$G'$のニム和は異なるので、$a\oplus b\oplus c=2^n-1$をみたす正整数$n$が存在することより$f(n-1)=0$または$f(n)=1$が成り立たなければなりません。しかし、$f(n-1)=0$のときは条件２、$f(n)=1$のときは条件３を満たさなくなるので、純粋な局面から純粋な局面に遷移することは出来ません。
次に、非自明で純粋ではない局面$H$から純粋な局面$H'$に必ず遷移できることを示します。まず、$f(m)=1$となるような最大の正整数$m$を取ります($H$は非自明な局面なので、このような$m$は必ず存在する)。
$\{g_{a}(m),g_{b}(m),g_{c}(m)\}=\{0,0,1\}$のとき
このとき、$a,b,c$の中に$g_{p}(m)=1$を満たすpが存在するので、$g_{p}(m)=0$として条件を満たすように構成できれば、純粋な局面に遷移することが出来ます。
$p' \equiv p \pmod{2^m}$、$q' \equiv q \pmod{2^m}$、$r' \equiv r \pmod{2^m}$$(0\leq p',q',r'\lt 2^m)$とすると、この条件を満たすように構成できないのは、次のいずれかが成り立つときです。
- $a,b,c$の中に$q'=0$を満たす$p$でない$q$が存在する。
- $a,b,c$の中に$q'=2^m-1$を満たす$p$でない$q$が存在する。
- $a,b,c$の中に$q'=r'$を満たす$p$でない$q,r$が存在する。
$p'\neq 2^m-1$のとき
1のみを満たすとき、$g_{q}(s)=1$となる最小の整数をとります($q\gt0$より必ず存在)。このとき、$s\gt m$より$f(s)=0$なので、$g_{p}(s)=1$または$g_{r}(s)=1$が成り立ちます。このとき、$p\oplus q\oplus r=2^{s+1}-1$となるように$p,r$のいずれかを操作すれば、純粋な局面に遷移することが出来ます。
2のみを満たすとき、もし$p'=r'$ならば、$p\oplus q\oplus r=2^{m+1}-1$で、$p,q,r$を$2^{m+1}$で割った余りを$p'',q'',r''$とするとこれらは互いに相異なる正整数であり、さらに$p,q,r$を$2^{m}$で割った余りは$p',q',r'$で、これは$p'=r'$を満たすので、$(p,q,r)$は純粋な局面であるから矛盾。
したがって、$p'\lt r'$または$p'\gt r'$であるから、$p',r'$のうち大きいほうから$\abs{p'-r'}$を減ずる操作を行えば、純粋な局面に遷移することが出来ます。
3のみを満たすとき、$g_{q}(t)\neq g_{r}(t)$を満たす$t(\gt m)$が必ず存在します。このとき、$f(t)=0$より$g_{p}(t)=1$なので、$p\oplus q\oplus r=2^{t+1}-1$となるように$p$を操作すれば、純粋な局面に遷移することが出来ます。
1,3をともに満たすときは、$s,t$のうち大きいほうに対して対応する操作を行えば純粋な局面に遷移することが出来ます。
($g_{p}(m)=1,g_{q}(m)=0,g_{r}(m)=0$より2については考えなくてもよい)。
$p'= 2^m-1$のとき
1のみを満たすとき、$g_{q}(i)=1$となる最小の整数$i$をとると、
- $m\lt j\lt i$かつ$g_{p}(j)=g_{q}(j)=g_{r}(j)=0$を満たす$j$が存在するとき、$p\oplus q\oplus r=2^{i+1}-1$となるように$p,r$のいずれかを操作すれば、純粋な局面に遷移することが出来ます。
- $m\lt j\lt i$かつ$g_{p}(j)=g_{q}(j)=g_{r}(j)=0$を満たす$j$が存在しないとき、$q$を$p\oplus q\oplus r=2^{i+1}-1$となるように操作すれば、操作後の$q,r$を$2^i$で割った余りは一致するので、純粋な局面に遷移することが出来ます。
2のみを満たすとき、$p'\neq 2^m-1$のときと同様に操作すれば、純粋な局面に遷移することが出来ます。
3のみを満たすとき、$p'\neq 2^m-1$のときと同様に操作すれば、純粋な局面に遷移することが出来ます。
1,3をともに満たすときは、$s,t$のうち大きいほうに対して対応する操作を行えば純粋な局面に遷移することが出来ます。
$\{g_{a}(m),g_{b}(m),g_{c}(m)\}=\{1,1,1\}$のとき
このとき、どの山からも$p\oplus q\oplus r=2^{m}-1$となる純粋な局面を構成できないのは、次のいずれかの条件を満たすときです。ただし、$p' \equiv p \pmod{2^m}$、$q' \equiv q \pmod{2^m}$、$r' \equiv r \pmod{2^m}$$(0\leq p',q',r'\lt 2^m)$、$0\lt w\lt 2^m-1$とします。
- $(p',q',r')=(0,0,w)$のとき
- $(p',q',r')=(0,0,2^m-1)$のとき
- $(p',q',r')=(0,w,2^m-1)$のとき
- $(p',q',r')=(w,w,w)$のとき
- $(p',q',r')=(w,w,2^m-1)$のとき
- $(p',q',r')=(w,2^m-1,2^m-1)$のとき
- $(p',q',r')=(2^m-1,2^m-1,2^m-1)$のとき
1,2,5のいずれかを満たすとき、$g_{r}(s)=1$となる最小の$s$をとり、$p\oplus q\oplus r=2^{s+1}-1$となるように$q$に操作を行うと、純粋な局面に遷移することが出来ます。
6を満たすとき、$g_{r}(s)=1$となる最小の$s$をとり、$p\oplus q\oplus r=2^{s+1}-1$となるように$p,q$のいずれかに操作を行うと、純粋な局面に遷移することが出来ます。
4,7を満たすとき、$p\not\equiv q,q\not\equiv r,r\not\equiv p\pmod{2^{t+1}}$を満たす最小の$t$をとります。このとき、対称性より$g_{p}(t)=g_{q}(t)=1$かつ$p''\equiv p\pmod{2^t}$、$q''\equiv q\pmod{2^t}$$(0\leq p''\lt q''\lt 2^t)$を満たすように$p,q$をとれ、
- $q''\neq 2^t-1$のとき、$p$を操作して$p\oplus q\oplus r=2^{t+1}-1$となるようにすれば、純粋な局面に遷移することが出来ます。
- $q''=2^t-1$のとき、$q$を操作して$p\oplus q\oplus r=2^{t+1}-1$となるようにすれば、純粋な局面に遷移することが出来ます。
3を満たすとき、$q$から$r'$個石を取ると、純粋な局面に遷移することが出来ます。
以上より、すべてのパターンについて、純粋な局面に遷移する方法を構成することが出来るので、非自明で純粋ではない局面$H$から純粋な局面$H'$に必ず遷移できることが示されました。
また、純粋な局面から自明な$\p$局面$(0,k,k)$に遷移することは出来ない(石の数を$0$個にするのと石の数を揃えるのでそれぞれ一手ずつ必要)ので、純粋な局面からは非自明で純粋でない局面または自明な$\n$局面にしか遷移できず、非自明で純粋でない局面からは必ず純粋な局面または自明な$\p$局面に遷移することが出来ます。
したがって、純粋な局面は$\p$局面に属することが示されました。
まとめ、今後の目標
今回分かったのは、次の事実です。
分配ニムは、2山ニムの$\p$局面または純粋な局面のときに、$\p$局面となる。ただし、純粋な局面とは、次の3つの条件を満たす局面のことである。
- $a\oplus b\oplus c=2^n-1$をみたす正整数$n$が存在する。
- $a,b,c$を$2^n$で割った余りを$a',b',c'(0\leq a',b',c'\lt 2^n)$とするとき、$a',b',c'$は互いに相異なる正整数である。
- $a,b,c$を$2^{n-1}$で割った余りを$a'',b'',c''(0\leq a'',b'',c''\lt 2^{n-1})$とするとき、$a'',b'',c''$の中に$0$が存在するまたは互いに等しい$2$数の組が存在する。
今後の目標は、山が4つのときの$\p$局面を知り、最終的に任意の数の山について$\p$局面を考えることです。また、今回は触れませんでしたが、grundy数がどうなるのかについても考えたいです。
終わりに
だいぶelephantかつ読み辛い証明になってしまったので、指摘や改善点などがあればぜひ教えてくださるとうれしいです。
今回扱ったニムなどのゲームは、実際に手を動かして考えられるので研究しやすい題材だと思います。競技数学にもよく出てくるので、その対策も兼ねて是非取り組んでみてはいかがでしょうか。
最後に、ここまで長い間読んでくださりありがとうございました。
おまけ
実は今日(2025年12月10日)誕生日でした。成人です。なんだか感慨深いですね。
誕生日！
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
