【論文602】ニムの勝ち負けは、繰り上がりのない足し算で決まる

要旨

ニムは、いくつかの山から交互に石を取り（一度に一つの山から好きなだけ）、最後の石を取った人が勝つ遊びである。どの局面が手番の人の負けかを、総当たりと式の二つの道筋で確かめる。新しい定理も法則も主張しない。

第一に、負けの局面は、繰り上がりのない足し算で見分けられる。山が三つ（それぞれ $0$〜$7$ 個）の $512$ 局面を総当たりで解くと、手番の人が負ける局面は $64$ 個（割合 $0.125000$）で、山の数を二進法で繰り上がりなしに足した値（排他的論理和）が $0$ の $64$ 局面とちょうど一致する。山が四つの $4096$ 局面でも $512$ 個で一致する（第2節）。

第二に、ふつうの足し算の偶奇では決まらない。「合計が偶数なら負け」と判定すると、$512$ 局面のうち当たるのは $320$（割合 $0.625000$）である。$(2,2,2)$ は合計 $6$ で偶数だが、繰り上がりのない和は $2$ で、手番の人が勝つ（第3節）。

第三に、勝ちの手は和から読める。$(3,4,5)$ の繰り上がりのない和は $2$ で、勝ちに通じる手は総当たりでもちょうど一つ、$3$ の山を $1$ にする手である（第3節）。

第四に、これが本稿の芯である。分離子は、繰り上がりがあるかである。二進法の各桁で $1$ の個数の偶奇だけを見る足し算なら、和が $0$ の局面からはどう取っても $0$ でなくなり、$0$ でない局面からは $0$ に戻す手が必ずある。繰り上がりのある足し算では、この二つが成り立たない（第3節）。

第五に、規則を変えても、足し算は変わらない。最後に取った人を負けにすると、負けの局面は $64$ 個のままで、ふつうのニムと違うのは山がすべて $1$ 以下の $8$ 局面だけである。一度に $1$〜$3$ 個しか取れないようにすると、山が三つ（$0$〜$9$ 個）の負けの局面 $252$ 個は、各山を $4$ で割った余りの繰り上がりのない和が $0$ の局面とちょうど一致する（第4節）。

第六に、替わるのは、足す相手である。上限つきでは、山の数そのものを足すと外れ、$4$ で割った余りを足すと当たる。足し算は同じで、各山を一つの数に置き換える規則だけが替わる（第4節）。

キーワード：ニム、組合せゲーム、排他的論理和、スプレイグ＝グランディの定理、必勝法。

射程（何を示さないか）

新しい定理も法則も主張しない。ニムの解（ブートン、$1901$）、一つの山を一つの数に置き換えれば和で決まるという定理（スプレイグ、$1935$／グランディ、$1939$）は、いずれも既知である。定理を証明しない。山が $0$〜$7$ 個（上限つきは $0$〜$9$ 個）の局面を総当たりで解き、式と局面ごとに突き合わせるだけである。戦略の計算量や、ほかの組合せゲームは扱わない。最後に取った人が負けの規則と、一度に取れる数に上限をつける規則だけを分離子の確かめに使う。既刊との関係：論文220 は、公正な硬貨 $X,Y$ の排他的論理和として $Z$ を作り、三つが二つずつは独立でも三つ一緒には独立でない例を示した。本稿では同じ排他的論理和が、ゲームの勝ち負けを決める。加えたのは、総当たりの負けの局面と繰り上がりのない和を局面ごとに突き合わせたこと、ふつうの足し算の偶奇がどれだけ外れるかを数で出したこと、規則を変えたとき替わるのは足し算ではなく足す相手だと二つの規則で確かめたことである。

1. 記法と問い

設定：山の石の数を $h_1,\dots,h_k$ とする。手番の人は一つの山を選び、$1$ 個以上好きなだけ取る。最後の石を取った人が勝ちである。最善を尽くしても手番の人が負ける局面を「負けの局面」と呼ぶ。

繰り上がりのない足し算：各山の数を二進法で書き、桁ごとに $1$ の個数の偶奇だけを残した数を

$$S=h_1\oplus h_2\oplus\cdots\oplus h_k$$

と書く（排他的論理和）。たとえば $3=011$、$4=100$、$5=101$ では、桁ごとの $1$ の個数は上の桁から $2,1,2$ で、偶奇を残すと $010$、つまり $S=2$ である。

問い：負けの局面は $S=0$ の局面と一致するか。ふつうの足し算ではなぜいけないか。規則を変えると何が替わるか。

2. 総当たりで解く

計算 2.1：局面ごとに「相手を負けの局面に送る手があるか」を、石の少ない局面から順に総当たりで決めた。

観察 2.2　数が同じなだけでなく、局面ごとに一致した。三つの山でも四つの山でも、総当たりの負けの局面の集合と $S=0$ の集合はちょうど同じである。総当たりは局面の木を全部たどり、$S$ は数を足すだけである。二つの道筋が同じ答を返す。

計算 2.3：山が三つで、各山が $0$〜$2^m-1$ 個のとき、$S=0$ の局面の割合は $m=1,2,3,4,5$ で $0.500000$、$0.250000$、$0.125000$、$0.062500$、$0.031250$ だった。二つの山を決めると三つ目が一つに決まるので、割合は $1/2^m$ になる。

3. ふつうの足し算ではいけない理由

計算 3.1：「合計が偶数なら負け」という判定を、三つの山の $512$ 局面で総当たりの答と比べた。当たるのは $320$ 局面（割合 $0.625000$）だった。

観察 3.2　$(2,2,2)$ は合計が偶数でも勝ちの局面である。一つの山を $0$ にすれば $(0,2,2)$ で $S=0$ になり、相手を負けの局面に送れる。ふつうの合計は $2+2+2=6$ で、下の桁の繰り上がりが上の桁に入り込む。繰り上がりのない和では、同じ桁の $1$ が三つあって $1$ が残る。

観察 3.3　勝ちの手は $S$ から読める。$(3,4,5)$ の $S=2$ は二進法で $010$ で、この桁に $1$ を持つ山は $3=011$ だけである。その山を $3\oplus2=1$ にすれば $S=0$ になる。総当たりで勝ちに通じる手を全部探しても、$(1,4,5)$ にする手ちょうど一つだった。

観察 3.4　これが本稿の芯である。分離子は、繰り上がりがあるかである。繰り上がりのない和では、一つの山だけを変えると $S$ も必ず変わるので、$S=0$ の局面からの手はすべて $S\neq0$ の局面へ行く。$S\neq0$ なら、$S$ のいちばん上の $1$ の桁に $1$ を持つ山を減らして $S=0$ にできる。ふつうの足し算では、一つの山を変えても合計の偶奇が変わらないことがあり（$2$ 個取れば偶奇は同じ）、この二つが成り立たない。

4. 規則を変える

計算 4.1：最後の石を取った人が負ける規則で、三つの山（各 $0$〜$7$ 個）を総当たりで解いた。負けの局面は $64$ 個で、ふつうのニムと違う局面は $8$ 個、すべての山が $1$ 以下の局面だけだった。その $8$ 局面では、$1$ の山が奇数個なら負けに入れ替わる（ブートンの規則）。総当たりの答はこの規則とちょうど一致した。

計算 4.2：一度に $1$〜$3$ 個しか取れない規則で、三つの山（各 $0$〜$9$ 個・$1000$ 局面）を総当たりで解いた。負けの局面は $252$ 個で、各山を $4$ で割った余りの繰り上がりのない和が $0$ の $252$ 局面とちょうど一致した。山の数そのものの和で判定すると一致しなかった。

観察 4.3　替わるのは、足し算ではなく足す相手である。上限つきでは、一つの山は「$4$ で割った余り」という一つの数に置き換わり、その数を繰り上がりなしに足す。これがスプレイグとグランディの定理の一例である。最後に取った人が負けの規則も、足し算は変えず、山がすべて $1$ 以下の終盤だけを入れ替える。

観察 4.4　論文220 と並べる。220 は $Z=X\oplus Y$ で、二つずつは独立でも三つ一緒には独立でない硬貨を作った。本稿では同じ演算が勝ち負けを決める。繰り上がりのない足し算は、桁ごとの偶奇だけを運ぶ演算である。

観察 4.5　言わないこと。ブートンの解もスプレイグ＝グランディの定理も証明しない。山が大きいときの計算の手間や、ほかの組合せゲームは扱わない。示したのは、小さい山の全局面で総当たりと式が局面ごとに一致すること、ふつうの足し算の偶奇がどれだけ外れるか、規則を変えたとき替わるのは足す相手だけであること、である。

5. 点呼と結び

1. 三つの山の $512$ 局面で負けは $64$（計算 2.1）：$S=0$ の $64$ と局面ごとに一致。
2. 四つの山の $4096$ 局面で負けは $512$（計算 2.1）：同じく一致。
3. 負けの割合は $1/2^m$（計算 2.3）：二つの山で三つ目が決まる。
4. 合計の偶奇で当たるのは $320/512$（計算 3.1）：割合 $0.625000$。
5. $(2,2,2)$ は偶数でも勝ち（観察 3.2）：繰り上がりが入り込む。
6. $(3,4,5)$ の勝ちの手は一つ（観察 3.3）：$3$ の山を $1$ に。
7. 分離子は繰り上がりがあるか（観察 3.4）：本稿の芯。
8. 最後に取ると負けでも、違うのは $8$ 局面（計算 4.1）：山がすべて $1$ 以下。
9. 上限つきの負け $252$ は、$4$ で割った余りの和（計算 4.2）：山の数の和では外れる。
10. 替わるのは足す相手（観察 4.3）：足し算は同じ。

結び：ニムは、山から交互に石を取り、最後を取った人が勝つ遊びである。負けの局面は、山の数を二進法で繰り上がりなしに足した値が $0$ の局面である。三つの山の $512$ 局面、四つの山の $4096$ 局面を総当たりで解くと、負けの局面 $64$ 個・$512$ 個は、この和が $0$ の局面と局面ごとに一致した。ふつうの足し算の偶奇では $512$ 局面のうち $320$ でしか当たらず、$(2,2,2)$ のように合計が偶数でも勝ちの局面がある。分離子は、繰り上がりがあるかである。繰り上がりのない和では、和が $0$ の局面からはどう取っても $0$ でなくなり、$0$ でない局面からは $0$ に戻す手が必ずある。規則を変えても、足し算は変わらない。最後に取った人が負けでも違うのは $8$ 局面だけで、一度に $1$〜$3$ 個しか取れないなら、足す相手が山の数から $4$ で割った余りに替わるだけだった。既刊との位置、論文220 が硬貨の独立を壊すのに使った排他的論理和が、ここでは勝ち負けを決める。正直に言えば、確かめたのは山が $0$〜$9$ 個までの全局面で、定理は証明していない。

参考文献

1. Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for your Mathematical Plays. Academic Press.
2. Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. Annals of Mathematics.
3. Grundy, P. M. (1939). Mathematics and games. Eureka.
4. Sprague, R. (1935). Über mathematische Kampfspiele. Tôhoku Mathematical Journal.
5. 山岸勇輝 (2026). 『「独立」は四つあり、たがいに何も言わない』[論文220]. Zenodo. 10.5281/zenodo.22119838

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「ニムの勝ち負けは、繰り上がりのない足し算で決まる」［論文602］. Zenodo.
DOI: 10.5281/zenodo.22805951

@misc{yamagishi2026yoi602,
  author = {Yamagishi, Yuuki},
  title = {Who Wins at Nim Is Decided by Addition Without Carries},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/602},
  doi = {10.5281/zenodo.22805951},
  note = {Preprint, edition 1}
}