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.
Scope (what is not claimed)
No new theorem or law is claimed——the solution of Nim (Bouton, $1901$) and the theorem that replacing each heap by one number decides the game by their sum (Sprague, $1935$; Grundy, $1939$) are known. The theorems are not proved——positions with heaps of $0$ to $7$ stones ($0$ to $9$ with the limit) are solved exhaustively and matched with the formula position by position. The cost of strategies and other combinatorial games are not treated——only the rule that the last taker loses and the rule limiting how many may be taken are used to check the separator. Relation to earlier papers: Paper 220 made $Z$ as the exclusive or of fair coins $X$ and $Y$, an example in which three variables are independent in pairs but not all together——here the same exclusive or decides who wins. What is added is matching exhaustive losing positions with the sum without carries position by position, giving in numbers how far the parity of the ordinary sum fails, and checking with two rules that what changes is not the addition but what is added.
1. Notation and the Question
Setting: let the heaps hold $h_1,\dots,h_k$ stones. The player to move chooses one heap and takes one or more stones from it; whoever takes the last stone wins. A position lost by the player to move even with best play is called a losing position.
Addition without carries: write each heap in binary and keep, in each digit, only the parity of the number of $1$s; write the result as
$$S=h_1\oplus h_2\oplus\cdots\oplus h_k$$(exclusive or). For $3=011$, $4=100$ and $5=101$ the numbers of $1$s in the digits are $2,1,2$ from the top; keeping parities gives $010$, that is $S=2$.
Question: do the losing positions coincide with those with $S=0$, why does the ordinary sum not work, and what changes when the rules change?
2. Solving Exhaustively
Computation 2.1: for each position, whether there is a move sending the opponent to a losing position was decided exhaustively, from positions with fewer stones upward.
| heaps | positions | losing by search | $S=0$ |
|---|---|---|---|
| three ($0$--$7$ each) | $512$ | $64$ | $64$ |
| four ($0$--$7$ each) | $4096$ | $512$ | $512$ |
Observation 2.2 not only the numbers but each position agrees. With three heaps and with four, the set of losing positions by search and the set with $S=0$ are exactly the same——the search follows the whole game tree; $S$ only adds numbers. The two routes give the same answer.
Computation 2.3: with three heaps of $0$ to $2^m-1$ stones, the share of positions with $S=0$ was $0.500000$, $0.250000$, $0.125000$, $0.062500$ and $0.031250$ for $m=1,2,3,4,5$. Two heaps determine the third, so the share is $1/2^m$.
3. Why the Ordinary Sum Does Not Work
Computation 3.1: the rule “lost if the total is even” was compared with the exhaustive answer over the $512$ positions with three heaps. It was right in $320$ (share $0.625000$).
| position | ordinary total | sum without carries $S$ | by search |
|---|---|---|---|
| $(1,2,3)$ | $6$ | $0$ | lost |
| $(2,2,2)$ | $6$ | $2$ | won |
| $(1,4,5)$ | $10$ | $0$ | lost |
| $(3,4,5)$ | $12$ | $2$ | won |
Observation 3.2 $(2,2,2)$ is won although its total is even. Emptying one heap gives $(0,2,2)$ with $S=0$, sending the opponent to a losing position——the ordinary total $2+2+2=6$ carries from the lower digit into the upper one; without carries, the same digit has three $1$s and a $1$ remains.
Observation 3.3 the winning move can be read from $S$. For $(3,4,5)$, $S=2$ is $010$ in binary, and the only heap with a $1$ in that digit is $3=011$. Making that heap $3\oplus2=1$ gives $S=0$——searching all winning moves exhaustively found exactly one, the move to $(1,4,5)$.
Observation 3.4 this is the core: the separator is whether there are carries. With the sum without carries, changing only one heap always changes $S$, so every move from $S=0$ goes to $S\neq0$. If $S\neq0$, reducing a heap that has a $1$ in the top digit of $S$ brings $S$ to $0$——with the ordinary sum, changing one heap may leave the parity of the total unchanged (taking $2$ keeps it), and neither of the two holds.
4. Changing the Rules
Computation 4.1: under the rule that whoever takes the last stone loses, three heaps of $0$ to $7$ were solved exhaustively. There were $64$ losing positions, differing from ordinary Nim in $8$ positions, exactly those in which every heap has at most $1$ stone. In those $8$, a position is lost when the number of heaps of $1$ is odd (Bouton’s rule), and the exhaustive answer agreed exactly with this rule.
Computation 4.2: under the rule that only $1$ to $3$ stones may be taken at once, three heaps of $0$ to $9$ ($1000$ positions) were solved exhaustively. There were $252$ losing positions, coinciding exactly with the $252$ in which the heaps’ remainders on division by $4$, added without carries, give $0$. Judging by the sum of the heap sizes themselves did not coincide.
Observation 4.3 what changes is not the addition but what is added. With the limit, each heap is replaced by one number, its remainder on division by $4$, and those numbers are added without carries——this is one instance of the theorem of Sprague and Grundy. The rule that the last taker loses also leaves the addition as it is and swaps only the endgame in which every heap has at most $1$ stone.
Observation 4.4 beside Paper 220. Paper 220 used $Z=X\oplus Y$ to make coins that are independent in pairs but not all together——here the same operation decides who wins. Addition without carries is the operation that carries only the parity of each digit.
Observation 4.5 what is not said. Neither Bouton’s solution nor the theorem of Sprague and Grundy is proved, and the cost of computation for large heaps and other combinatorial games are not treated——what is shown is that on all positions with small heaps the search and the formula agree position by position, how far the parity of the ordinary sum fails, and that changing the rules changes only what is added.
5. Roll Call and Closing
- $64$ losing positions among $512$ with three heaps (Computation 2.1): matching the $64$ with $S=0$ position by position.
- $512$ losing positions among $4096$ with four heaps (Computation 2.1): matching likewise.
- the losing share is $1/2^m$ (Computation 2.3): two heaps fix the third.
- parity of the total is right in $320/512$ (Computation 3.1): share $0.625000$.
- $(2,2,2)$ is won though even (Observation 3.2): a carry gets in.
- one winning move from $(3,4,5)$ (Observation 3.3): the heap of $3$ to $1$.
- the separator is whether there are carries (Observation 3.4): the core.
- if the last taker loses, $8$ positions differ (Computation 4.1): every heap at most $1$.
- $252$ losing positions with the limit, by remainders mod $4$ (Computation 4.2): the sum of sizes fails.
- what changes is what is added (Observation 4.3): the addition is the same.
Closing: Nim is a game of taking stones in turn from heaps, won by whoever takes the last. The losing positions are those whose heap sizes, added in binary without carries, give $0$——solving the $512$ positions with three heaps and the $4096$ with four exhaustively, the $64$ and $512$ losing positions coincided position by position with those where this sum is $0$. The parity of the ordinary sum is right in only $320$ of the $512$, and there are won positions with an even total, such as $(2,2,2)$. The separator is whether there are carries——with the sum without carries, every move from sum $0$ leaves a nonzero sum, and from a nonzero sum there is always a move back to $0$. Changing the rules does not change the addition——if the last taker loses, only $8$ positions differ, and if only $1$ to $3$ stones may be taken, what is added simply changes from the heap sizes to their remainders by $4$. Placed among the earlier papers——the exclusive or that Paper 220 used to break the independence of coins here decides who wins. To be honest——what was checked is every position with heaps of up to $9$ stones; the theorems were not proved.
References
- Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for your Mathematical Plays. Academic Press.
- Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. Annals of Mathematics.
- Grundy, P. M. (1939). Mathematics and games. Eureka.
- Sprague, R. (1935). Über mathematische Kampfspiele. Tôhoku Mathematical Journal.
- Yamagishi, Y. (2026). There Are Four Independences, and They Say Nothing to One Another [Paper 220]. Zenodo. 10.5281/zenodo.22119838
Reference
Yamagishi, Y. (2026). Who Wins at Nim Is Decided by Addition Without Carries [Paper 602]. YOI: https://www.yamagishiyuuki.com/yoi/602
DOI: 10.5281/zenodo.22805951
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 602. This paper is a preprint and has not been peer reviewed.