Impartial Combinatorial Games

Prerequisite: Introduction to Game Theory

This article discusses impartial combinatorial games.

Among impartial combinatorial games, the most fundamental and important is the normal Nim game. The Sprague–Grundy theorem states that all impartial combinatorial games under normal play are equivalent to a single-pile Nim game. From this, the concepts of the Sprague–Grundy function and nimbers can be developed, which completely characterize an impartial combinatorial game under normal play. Therefore, this article first establishes the conclusions for normal Nim games and Sprague–Grundy theory. Subsequently, it discusses some common impartial combinatorial games in algorithmic competitions.

Finally, this article briefly discusses misère Nim games. Misère games are much more complex than normal games and rarely appear in algorithmic competitions. Unless otherwise specified, the games mentioned in this article are assumed to be normal impartial combinatorial games.

「State」, 「Position」, and 「Game」

This article will use these three terms interchangeably. In game theory, the state of a game usually includes all information that may be relevant to the game up to a certain point. In general, the state of a game often includes the past actions of both players, the realized values of random variables, the content of known information for both sides, etc. The term position is relatively less standard in game theory and usually refers to the situation faced by both players at a certain moment in the game, such as the positions of pieces in a board game. Only for impartial combinatorial games (or more generally, zero-sum, deterministic, perfect-information games), since the game involves no randomness and the set of future actions and payoff functions for players are independent of the historical path (i.e., previous actions of both sides) that led to the current position, there is no distinction between the state and the position of the game, and both can be viewed as a node in the game graph. Since a game can always be described by its initial position, the term "position" is sometimes used directly to refer to the game itself.

Nim Game

The rules of the Nim game are simple:

Nim Game

There are $n$ piles of stones, the $i$-th pile has $a_i$ stones. Two players take turns removing any number of stones from any single pile, but they must remove at least one stone. The player who takes the last stone wins.

It is easy to verify that Nim is an impartial combinatorial game under normal play.

Example

For example, currently there are $3$ piles of stones with counts $2,5,4$. Then, one can take $2$ stones from the first pile, resulting in the position $0, 5, 4$; or take $4$ stones from the second pile, resulting in $2, 1, 4$. If at some point the position becomes $0, 0, 5$, and player A takes the $5$ stones from the third pile, i.e., takes the last stone, then player A wins.

Game Graph and States

In Nim, the possible changes of positions can be described by a game graph.

Treat each possible state as a node in a graph, and connect a state to its successor states (states reachable by a single move) with directed edges, resulting in a directed acyclic graph—the game graph. The graph is acyclic because in Nim, the total number of stones strictly decreases with each move.

Example

For example, for a Nim game with initial position having $3$ piles of stones with counts $1,1,2$, the following game graph can be drawn:

Example of a game graph

As will be mentioned shortly, red nodes in the graph represent winning positions, and black nodes represent losing positions.

Since Nim is an impartial combinatorial game, whether a player has a winning strategy depends only on the current state of the game, not on the player's identity. Therefore, all states can be classified as (first-player) winning positions and (first-player) losing positions, denoted as $\mathcal N$ positions and $\mathcal P$ positions[^n-vs-p] respectively. This definition applies to all impartial combinatorial games.

The following lemma allows all states to be inductively marked as winning or losing positions:

Lemma

In an impartial combinatorial game under normal play,

A state with no successors is a losing position $\mathcal P$,
A state is a winning position $\mathcal N$ if and only if at least one of its successors is a losing position $\mathcal P$,
A state is a losing position $\mathcal P$ if and only if all its successors are winning positions $\mathcal N$.

Proof

For the first point, if a player currently has no legal moves, the player has lost the game.

For the second point, if the state has at least one successor that is a losing position, the player can move to that losing position; then the opponent faces a first-player losing position, and the player wins.

For the third point, if no successor is a losing position, then any move leads to a winning position; then the opponent faces a first-player winning position, and the player loses.

In all impartial combinatorial games, the game graph is a directed acyclic graph. Therefore, using these three properties, after constructing the game graph, one can compute whether each state is winning or losing in $O(|V|+|E|)$ time, where $|V|$ is the number of states and $|E|$ is the number of edges, i.e., the total number of possible moves from all states.

This lemma can be generalized to misère games and directed graphs that may have cycles. Related discussion can be found in the section Games on Directed Graphs.

Nim-sum

Let's continue examining the Nim game.

By drawing the game graph, one can determine whether a given position is a first-player winning position in $\Omega(\prod_{i=1}^na_i)$ time. However, this complexity is too high for practical use. In fact, it can be found that whether a Nim position is a first-player winning position depends only on the Nim-sum of the current pile sizes.

Nim-sum

The Nim-sum of natural numbers $a_1,a_2,\cdots,a_n$ is defined as $a_1\oplus a_2\oplus\cdots\oplus a_n$.

The Nim-sum is simply the bitwise XOR operation.

Theorem

In Nim, the state $(a_1,a_2,\cdots,a_n)$ is a losing position $\mathcal P$ if and only if the Nim-sum

\[ a_1\oplus a_2\oplus\cdots\oplus a_n = 0. \]

Proof

Apply induction on all possible states:

If $a_i=0$ for all $i=1,\cdots,n$, this state has no successors, and its Nim-sum is $0$, so the statement holds.
If $k = a_1\oplus a_2\oplus\cdots\oplus a_n\neq 0$, we need to show the state is winning. That is, we need to construct a legal move that leads to a losing position; by the induction hypothesis, it suffices to show that the successor state satisfies $a'_1\oplus a'_2\oplus\cdots\oplus a'_n=0$. Using properties of Nim-sum (i.e., XOR), this is equivalent to saying there exists a pile $i$ such that by removing some stones from $a_i$, we can obtain $a_i\oplus k$, i.e., $a_i>a_i\oplus k$.

Indeed, let $d$ be the highest bit where $k$ has a $1$. Then there must exist some $a_i$ whose $d$-th bit is $1$. For that pile, we have $a_i>a_i\oplus k$, because $a_i\oplus k$ has the $d$-th bit as $0$ and higher bits same as $a_i$.
If $a_1\oplus a_2\oplus\cdots\oplus a_n= 0$, we need to show the state is losing. By the induction hypothesis, it suffices to show that all its successors have Nim-sum not equal to $0$. This is inevitable: any legal move changing $a_i$ to $a'_i\neq a_i$ will change the Nim-sum to $a'_i\oplus a_i\neq 0$.

Thus, one can determine whether a Nim position is a first-player winning position in $O(n)$ time.

Sprague–Grundy Theory

Sprague–Grundy theory states that all impartial combinatorial games are equivalent to a single-pile Nim game. This conclusion is mainly applied in scenarios where the game consists of multiple independent subgames. In such cases, determining the state of the game can be done by computing the Nim-sum of the SG function values of the subgames. If the game itself does not have such a structure, then determining winning and losing positions only requires applying the lemma from the game graph section earlier.

Notation for Games

As mentioned earlier, all impartial combinatorial games can be described by drawing a game graph. Since the nature of each state in the game graph is determined solely by its successors, a state $S$ can be represented by the set of its successor states.

Example (continued)

Continuing the previous game graph example, we obtain the following state representations:

\[ \begin{aligned} S_{0,0,0} &= \{\},\\ S_{0,1,0} &= \{S_{0,0,0}\} = \{\{\}\},\\ S_{0,0,1} &= \{S_{0,0,0}\} = \{\{\}\},\\ S_{0,0,2} &= \{S_{0,0,0},S_{0,0,1}\} = \{\{\},\{\{\}\}\},\\ S_{0,1,1} &= \{S_{0,0,0},S_{0,1,0},S_{0,0,1}\} = \{\{\},\{\{\}\}\},\\ S_{0,1,2} &= \{S_{0,0,2},S_{0,1,0},S_{0,1,1}\} = \{\{\{\}\},\{\{\},\{\{\}\}\}\}. \end{aligned} \]

Here, $S_{0,1,0}=S_{0,0,1}$, $S_{0,0,2}=S_{0,1,1}$.

A game can be represented by its initial state.

Although the representation of impartial games can be quite complex, single-pile Nim games are relatively simple. With one pile of $n$ stones, it can be represented as

\[ *0 = \{\},~*n = \{*m : m<n,~m\in\mathbf N\} = \{*0,*1,\cdots,*(n-1)\}. \]

Here, the notation $*n$ denotes the single-pile Nim game (initial state) with $n$ stones.

Example (continued)

Using this notation, the states in the above example can be simply written as

\[ S_{0,0,0} = *0,~ S_{0,1,0} = S_{0,0,1} = *1,~ S_{0,0,2} = S_{0,1,1} = *2,~ S_{0,1,2} = \{*1, *2\}. \]

In subsequent discussion, the notation $T\in S$ should be understood as state $T$ being a successor of state $S$.

Sum and Equivalence of Games

The equivalence relation for games relies on the concept of the sum[^more-sums] of games.

Sum of Games

The sum (or combined game) of games $G$ and $H$, denoted $G+H$, is the game

\[ G + H = \{g + H : g \in G\} \cup \{G + h : h \in H\}. \]

The sum of games can be understood as a game consisting of two subgames played simultaneously and independently, where at each turn a player must make a move in exactly one of the subgames, and the game ends when no moves are possible in either subgame. The concept of game sum generalizes to any number of games, and it is associative and commutative—meaning the result of combining multiple games is independent of the order of combination and the order of the games. Nim with multiple piles is the sum of multiple single-pile Nim games.

An observation is that although in single-pile Nim, all positions except the empty pile are first-player winning, these different single-pile Nim games are not equivalent when combined with other single-pile Nim games. For example, the game $*n$ only yields a losing game when combined with another $*n$; combined with any other $*n'\neq *n$, the resulting game is winning.

This observation suggests that one can study the properties of a game by examining its sum with other games. This leads to the notion of equivalence of games.

Equivalence of Games

If for every game $H$, the games $G_1+H$ and $G_2+H$ are either both losing or both winning, then games $G_1$ and $G_2$ are said to be equivalent, denoted $G_1\approx G_2$.

It is easy to verify that $\approx$ defined this way is indeed an equivalence relation on the set of all impartial games.

Sprague–Grundy Function

The analysis of Nim shows that different single-pile Nim games are not equivalent. However, all impartial games are equivalent to some single-pile Nim game. Thus, we can assign a number to each impartial game—this is the Sprague–Grundy function.

To prove these results, we first need two lemmas about game equivalence. First, combining a losing game with any game yields a game equivalent to the original.

Lemma 1

For any game $G$ and any losing game $A\in\mathcal P$, we have $G\approx G + A$.

Proof

By definition, we need to show that for any game $H$, $G+H\approx G+A+H$ holds.

If $G+H$ has a winning strategy, then $G+A+H$ also has a winning strategy. If the opponent moves in subgame $A$, respond by moving to restore it to a losing position; otherwise, follow the winning strategy in $G+H$. This ensures eventual victory.

If $G+H$ is a losing game, then $G+A+H$ is also a losing game. Because regardless of whether the move is in $G+H$ or $A$, the opponent can respond in the next turn to restore the corresponding subgame to a losing position. Eventually, the first player cannot win.

Second, two games are equivalent if and only if their sum is a losing game. This lemma provides a method to prove equivalence of two games.

Lemma 2

Games $G$ and $G'$ are equivalent if and only if $G+G'\in\mathcal P$ is a losing game.

Proof

If $G$ and $G'$ are equivalent, then $G+G'\approx G+G$, and $G+G$ is a losing game. This is because for any move by the first player, the second player can mimic the move in the other subgame, and eventually the first player will have no move.

Conversely, if $G+G'$ is a losing game, then by Lemma 1, $G\approx G+(G+G') = (G+G)+G' \approx G'$.

Using these lemmas, we obtain the following theorem:

Theorem (Sprague–Grundy)

For any (finite) impartial game $G$, there exists $n\in\mathbf N$ such that $G\approx *n$.

Proof

We prove by induction. Let $G = \{G_1,G_2,\cdots,G_k\}$. By the induction hypothesis, there exist $n_1,n_2,\cdots,n_k$ such that $G_i\approx *n_i$. Consider the game

\[ G' = \{*n_1,*n_2,\cdots,*n_k\}. \]

We will show that $G'\approx *m$, where $m=\operatorname{mex}\{n_1,n_2,\cdots,n_k\}$ is the smallest natural number not appearing in the set.

First, we show $G\approx G'$. By Lemma 2, it suffices to show $G+G'$ is a losing game. Assume $G\neq *0$. If the first player moves to $G_i$, the second player can move to $*n_i$; conversely, if the first player moves to $*n_i$, the second player can move to $G_i$. After these two moves, the game becomes $G_i+*n_i$, which by Lemma 2 and $G_i\approx *n_i$ is a losing game. Hence $G\approx G'$.

Second, we show $G'\approx*m$. By Lemma 2, it suffices to show $G'+*m$ is a losing game. Assume $G'\neq *0$. If the first player moves to $*n_i\in *m$, then by definition of $m$, the second player can move to $*n_i\in G'$, making the position $*n_i + *n_i\in\mathcal P$, a losing position for the first player. If the first player moves to $*n_i\in G$ with $n_i<m$, then the second player can move to $*n_i\in *m$, again resulting in $*n_i+*n_i\in\mathcal P$. Finally, if the first player moves to $*n_i\in G$ with $n_i>m$, then the second player can move to $*m\in *n_i$, resulting in $*m+*m\in\mathcal P$. Thus $G'\approx *m$.

By transitivity of equivalence, $G\approx *m$. This completes the induction, proving that every game $G$ is equivalent to a single-pile Nim game.

This result shows that we can assign a natural number $n$ to each impartial game $G$ such that $G\approx *n$.

Nimber

The nimber of an impartial game $G$ is the unique natural number $n$ such that $G\approx *n$.

This function mapping impartial games to nimbers is called the Sprague–Grundy function (SG function for short), denoted $\operatorname{SG}(\cdot)$. Since each state of an impartial game is itself an impartial game, we can compute the corresponding nimber (SG value) for each state.

From the proof of the theorem, the Sprague–Grundy function can be computed recursively as follows:

Corollary

The Sprague–Grundy function value $\operatorname{SG}(x)$ for a state $x$ in an impartial game $G$ satisfies

\[ \operatorname{SG}(x) = \operatorname{mex}\{\operatorname{SG}(x'): x'\in x\}. \]

Here, $\operatorname{mex}(A):=\min\{n\in\mathbf N:n\notin A\}$ is the minimum excluded value, the smallest natural number not in set $A$.

That is, the SG value of a state is the $\operatorname{mex}$ of the SG values of all its successors.

Using SG values (nimbers), we can determine whether a state is a first-player winning position.

Corollary

A state $x$ in an impartial game $G$ is a first-player winning position if and only if $\operatorname{SG}(x)\neq 0$.

Finally, the SG value of a sum of games is the Nim-sum (XOR) of the SG values of the subgames.

Theorem (Sprague–Grundy)

For impartial games $G_1,G_2,\cdots,G_n$, we have

\[ \operatorname{SG}(G_1+ G_2+\cdots + G_n) = \operatorname{SG}(G_1)\oplus \operatorname{SG}(G_2)\oplus\cdots\oplus\operatorname{SG}(G_n). \]

Proof

Since $*a_1+ *a_2 + \cdots + *a_n$ is the Nim game with pile sizes $(a_1,a_2,\cdots,a_n)$, by the Nim result, the game

\[ *a_1+ *a_2 + \cdots + *a_n + *(a_1\oplus a_2\oplus\cdots\oplus a_n) \]

is a first-player losing game. By Lemma 2, we have

\[ *a_1+ *a_2 + \cdots + *a_n \approx *(a_1\oplus a_2\oplus\cdots\oplus a_n). \]

Thus,

\[ \operatorname{SG}(*a_1 + *a_2 + \cdots + *a_n) = a_1\oplus a_2\oplus\cdots\oplus a_n. \]

Let $a_i=\operatorname{SG}(G_i)$, so $G_i\approx *a_i$. Then using algebraic properties of $\approx$, we have

\[ (G_1+ G_2+\cdots + G_n) + (*a_1 + *a_2 + \cdots + *a_n) = \sum_{i=1}^n(G_i+*a_i) \in\mathcal P. \]

Therefore,

\[ \begin{aligned} \operatorname{SG}(G_1+ G_2+\cdots + G_n) &= \operatorname{SG}(*a_1 + *a_2 + \cdots + *a_n) \\ &= a_1\oplus a_2\oplus \cdots \oplus a_n \\ &= \operatorname{SG}(G_1)\oplus \operatorname{SG}(G_2)\oplus\cdots\oplus\operatorname{SG}(G_n). \end{aligned} \]

This theorem greatly simplifies the computation of SG values for sums of games.

Thus, we can summarize the method for computing SG values:

For multiple independent games, compute their SG values separately, then take the Nim-sum;
For a single game, the SG value of each state is the $\operatorname{mex}$ of the SG values of all its successors;
In particular, terminal states (states with no successors) have SG value $\operatorname{mex}\varnothing = 0$.

Nimbers

Every impartial game corresponds uniquely to a nimber. The set of (finite) nimbers is the set of natural numbers $\mathbf N$. However, its algebraic structure differs from that of natural numbers. Specifically, two operations can be defined on nimbers: Nim-sum $\oplus$ and Nim-product $\otimes$:

Operations on Nimbers

For nimbers $a,b$, define:

Nim-sum $a\oplus b=\operatorname{mex}(\{a'\oplus b:a'<a,~a'\in\mathbf N\}\cup\{a\oplus b':b'<b,~b'\in\mathbf N\})$,
Nim-product $a\otimes b=\operatorname{mex}(\{(a'\otimes b)\oplus(a\otimes b')\oplus(a'\otimes b'):a'<a,~b'<b,~a',b'\in\mathbf N\})$.

The set of all nimbers under $\oplus$ and $\otimes$ forms a field of characteristic $2$ field. Moreover, these operations and their inverses are closed for the first $2^{2^n}$ nimbers; this yields a series of finite fields $\mathbf F_{2^{2^n}}$ of size $2^{2^n}$ finite fields.

Common Impartial Games

Although Sprague–Grundy theory completely solves impartial games, directly applying the theorem to compute SG values is often inefficient for practical games. For example, in Nim, brute-force computation of SG values has exponential complexity. Therefore, it is often necessary to guess conclusions for specific games by generating tables.

This section lists some common impartial games and their conclusions. When stating results, only the criteria for winning and losing positions are given. As for winning strategies, they involve making appropriate moves to leave the opponent in a losing position. Since variants of these games frequently appear in algorithmic competitions, understanding the proof process for each game's conclusion is also important.

Proof Methods for This Section's Conclusions

The proofs in this section are verification-style. For a game, the conclusion describes its first-player losing and winning positions. In the proof, we only need to verify that from a first-player losing position, only winning positions can be reached; and from a first-player winning position, at least one losing position can be reached. To turn these verifications into rigorous proofs, one needs to construct the game graph and apply mathematical induction on the states, with these verification steps serving as the inductive part.

Bachet's Game

Compared to single-pile Nim, Bachet's game restricts the number of stones that can be taken each turn.

Bachet's Game

There is a pile of $n$ stones. Two players take turns removing at least $1$ and at most $k$ stones. The player who takes the last stone wins.

The following result holds:

Theorem

The first player loses if and only if $n\equiv 0\pmod {k+1}$.

Proof 1

If $n\not\equiv 0\pmod {k+1}$, the first player can take $n\bmod{(k+1)}\in[1,k]$ stones, leaving the opponent in a losing position. Thus it is a winning position.

Conversely, if $n\equiv 0\pmod {k+1}$, then either there is no move, or after the first player removes $k'$ stones, the opponent can remove $k+1-k'$ stones, returning the first player to a losing position.

Proof 2

As an application of Sprague–Grundy theorem, compute $f(n)$ as the SG value when $n$ stones remain.

For $n\le k$, we can inductively prove $f(n)=n$. This is the same as single-pile Nim because the restriction on moves doesn't take effect. For $n>k$, we can prove $f(n)=n\bmod{(k+1)}$, so

\[ f(n) = \operatorname{mex}\{f(n-k),f(n-k+1),\cdots,f(n-1)\}. \]

This traverses all residues modulo $k+1$ except $n\bmod{(k+1)}$. Hence $f(n) = n\bmod{(k+1)}$.

Moore's Nim-$k$ Game

Compared to Nim, Moore's Nim-$k$ allows removing stones from up to $k$ piles in one turn.

Moore's Nim-$k$ Game

There are $n$ piles of stones, the $i$-th pile has $a_i$ stones. Two players take turns removing any number of stones from at least $1$ and at most $k$ piles, but must remove at least one stone. The player who takes the last stone wins.

The following result holds:

Theorem

Write each pile size in binary. For each bit position $d$, count how many piles have a $1$ in that bit, and compute this count modulo $(k+1)$. If for every bit position this remainder is $0$, then the first player loses; otherwise, the first player wins.

Proof

Mimicking the proof for Nim, this can be easily proved. Let $d$ be the highest bit where the remainder is non-zero, with remainder $k'\le k$. The winning strategy is to choose $k$ piles among those with a $1$ in bit $d$, and choose the number of stones to remove such that in the opponent's position, every bit's remainder becomes $0$. The only thing to verify is that such a choice is always possible.

Indeed, by selecting $k'$ piles and removing $2^d$ stones from each, the remainder for bit $d$ becomes $0$. For lower bits, assign the remainders arbitrarily to one of the chosen piles.

Staircase Nim Game

Staircase Nim is slightly more complex, allowing stones to move between adjacent piles.

Staircase Nim Game

There are $n$ piles of stones, the $i$-th pile has $a_i$ stones. Two players take turns. In each turn, a player may either remove any number of stones from the first pile, or move any number of stones from pile $i>1$ to pile $i-1$, but must make a move. The player who takes the last stone wins.

The following result holds:

Theorem

The first player loses if and only if the Nim-sum of the odd-indexed piles $a_1\oplus a_3\oplus\cdots\oplus a_{n-1+(n\bmod 2)}=0$.

Proof

When a player moves stones from an even-indexed pile to an odd-indexed pile, the opponent can move those stones to the next even-indexed pile (or remove them), so such moves do not affect the odd-indexed piles. Here, each odd-indexed pile moving down to the adjacent even-indexed pile (or being removed) can be viewed as an independent single-pile Nim game. By the Sprague–Grundy theorem for sums, the SG value of Staircase Nim is the Nim-sum of the SG values of these subgames, yielding the above conclusion.

Fibonacci Nim Game

Fibonacci Nim is similar to Bachet's game: there is one pile, and the number of stones that can be taken is restricted. Unlike Bachet, the restriction in Fibonacci Nim is dynamic.

Fibonacci Nim Game

There is a pile of $n$ stones. Two players take turns removing stones. The first player may remove any positive number of stones but not all; thereafter, each player may remove at most twice the number of stones removed by the opponent in the previous turn. The number removed must be positive. The player who takes the last stone wins.

The following result holds:

Theorem

At the start, the first player loses if and only if the number of stones $n$ is a Fibonacci number.

Proof

Let $q$ be the current quota (maximum number of stones that can be removed). In the first turn, $q=n-1$; later, $q$ is twice the number removed by the opponent in the previous turn. Consider the Fibonacci representation of the remaining stones $n$, i.e., the unique decomposition of $n$ into a sum of distinct, non-consecutive positive Fibonacci numbers. We need to show that the current state is winning if and only if $q$ is at least the smallest Fibonacci number in the decomposition of $n$.

The winning strategy is: if possible, remove all remaining stones; otherwise, remove the smallest Fibonacci number in the decomposition. Since in the decomposition, the next smallest Fibonacci number is strictly more than twice the smallest, if the current winning player cannot take all stones, the opponent in the next turn cannot take the next smallest Fibonacci number (which becomes the smallest), so the opponent will be in a losing position.

Conversely, if currently in a losing position, let $k$ be the number removed, which must be strictly less than the smallest Fibonacci number $F$ in the decomposition. Suppose the smallest Fibonacci number in the next turn is $F'$, which is also the smallest in the decomposition of $F - k$. Let $F'=F''+F'''$ with $F''>F'''$, i.e., $F''',F'',F'$ are three consecutive Fibonacci numbers. If $k<F''$, then when computing $k + (F-k)$ using Fibonacci representation, no carry occurs, so $F$ cannot be obtained. Thus $k\ge F''$. This implies the next turn's quota $2k>F''+F'''=F'$, a winning position.

Wythoff's Game

Wythoff's game allows removal from multiple piles simultaneously, but requires removing the same number from each.

Wythoff's Game

There are two piles of stones, with $a_1$ and $a_2$ stones respectively. Two players take turns removing stones from one pile or both piles. When removing from both, the same number must be taken from each. At least one stone must be taken. The player who takes the last stone wins.

The following result holds:

Theorem

Assume $a_1\le a_2$. Then the first player loses if and only if $a_1 = \lfloor(a_2-a_1)\phi\rfloor$, where $\phi=(\sqrt{5}+1)/2$ is the golden ratio.

To prove this, we need the following lemma:

Beatty Sequence

Let $r > 1$ be irrational. The Beatty sequence generated by $r$ is $\mathcal B_r = \{\lfloor kr\rfloor : k \in\mathbf N_+\}$.

Rayleigh Theorem

Let $r,s > 1$ be irrational numbers such that $\dfrac{1}{r}+\dfrac{1}{s}=1$. Then the sequences $\mathcal B_r$ and $\mathcal B_s$ partition the positive integers $\mathbf N_+$. They are called complementary Beatty sequences.

Proof

Let $\mathcal A_r=\{kr:k\in\mathbf N_+\}$. Consider sorting the elements of $\mathcal A=\mathcal A_r\cup\mathcal A_\ell$ into a sequence $\{a_i\}_{i\in\mathbf N_+}$. We need to show that $i=\lfloor a_i\rfloor$ for all $i\in\mathbf N_+$, which implies $\mathcal B_r\cup\mathcal B_s$ partitions $\mathbf N_+$.

First, show there are no duplicate elements. Suppose otherwise, there exist $k,\ell\in\mathbf N_+$ such that $kr=\ell s$. Then

\[ \dfrac{\ell}{k} = \dfrac{r}{s} = r - 1. \]

But the left side is rational, the right side irrational, contradiction. Hence all numbers are distinct.

Next, show there are exactly $\lfloor a_i\rfloor$ numbers in $\mathcal A$ less than or equal to $a_i$. Assume $a_i\in\mathcal A_r$, i.e., $a_i=kr$. Counting elements in $\mathcal A_r$ and $\mathcal A_\ell$ separately, the number of positive integers less than or equal to $a_i$ is

\[ k + \left\lfloor\dfrac{kr}{s}\right\rfloor = k + \lfloor k(r-1)\rfloor = \lfloor kr\rfloor = \lfloor a_i\rfloor. \]

Since $\{a_i\}$ is strictly increasing, there are exactly $i$ numbers less than or equal to $a_i$. Thus $i=\lfloor a_i\rfloor$.

Now we can prove the Wythoff result.

Proof of Wythoff's Game Conclusion

For all first-player losing positions $(a_1,a_2)$ with $a_1 < a_2$, let $k = a_2 - a_1 \in\mathbf N_+$. Then $a_1=\lfloor k\phi\rfloor$ and $a_2=\lfloor k(\phi+1)\rfloor$. Since $\phi$ is the golden ratio, $\dfrac{1}{\phi}+\dfrac{1}{\phi+1}=1$. By Rayleigh's theorem, the sequences $\{\lfloor k\phi\rfloor\}$ and $\lfloor k(\phi+1)\rfloor$ partition $\mathbf N_+$. This means that in all first-player losing positions $(a_1,a_2)$ with $a_1<a_2$, the components $a_1$ and $a_2$ each take every positive integer exactly once, and their difference $a_2-a_1$ also takes every positive integer exactly once.

In Wythoff, a legal move either keeps one component unchanged or keeps the difference unchanged. So from a first-player losing position, no legal move leads to another first-player losing position. Conversely, for any first-player winning position $(a_1,a_2)$, assume $a_1\le a_2$ and let $k=a_2

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

Impartial Combinatorial Games

Nim Game

Game Graph and States

Nim-sum

Sprague–Grundy Theory

Notation for Games

Sum and Equivalence of Games

Sprague–Grundy Function

Nimbers

Common Impartial Games

Bachet's Game

Moore's Nim-\(k\) Game

Staircase Nim Game

Fibonacci Nim Game

Wythoff's Game