YOI 602：ニムの勝ち負けは、繰り上がりのない足し算で決まる

論文602 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/602 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.22805951）。

本文はサイトの記事でも読めます：【論文602】ニムの勝ち負けは、繰り上がりのない足し算で決まる

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969434・969435・969440・969461 に記録されました（2026年10月01日 18:16（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、負けの局面は、繰り上がりのない足し算で見分けられる。山が三つ（それぞれ $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節）。

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

Abstract

Nim is a game in which players take stones in turn from heaps (from one heap at a time, as many as they like), and whoever takes the last stone wins.Which positions are lost for the player to move is checked by two routes, exhaustive search and a formula.No new theorem or law is claimed.

First, losing positions are recognised by addition without carries、solving the $512$ positions with three heaps of $0$ to $7$ stones exhaustively, the positions lost by the player to move number $64$ (share $0.125000$) and coincide exactly with the $64$ positions whose heap sizes, added in binary without carries (exclusive or), give $0$. With four heaps, the $4096$ positions give $512$ and again coincide (Section 2).

Second, the parity of the ordinary sum does not decide it、judging “lost if the total is even” is right in $320$ of the $512$ positions (share $0.625000$). $(2,2,2)$ has the even total $6$, but its sum without carries is $2$ and the player to move wins (Section 3).

Third, the winning move can be read from the sum、the sum without carries of $(3,4,5)$ is $2$, and exhaustive search finds exactly one winning move, reducing the heap of $3$ to $1$ (Section 3).

Fourth, and this is the core.The separator is whether there are carries、with an addition that keeps only the parity of the number of $1$s in each binary digit, every move from a position with sum $0$ leaves a nonzero sum, and from a nonzero sum there is always a move back to $0$. With carries, neither holds (Section 3).

Fifth, changing the rules does not change the addition、if the last taker loses, the losing positions remain $64$, differing from ordinary Nim only in the $8$ positions where every heap has at most $1$ stone. If only $1$ to $3$ stones may be taken at once, the $252$ losing positions with three heaps of $0$ to $9$ coincide exactly with those where the heaps’ remainders on division by $4$, added without carries, give $0$ (Section 4).

Sixth, what changes is what is added、with the limit, adding the heap sizes themselves fails and adding their remainders by $4$ succeeds. The addition is the same; only the rule replacing each heap by one number changes (Section 4).

Keywords: Nim, combinatorial game, exclusive or, Sprague-Grundy theorem, winning strategy

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/602/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/602 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ