Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

Single Pile Games

October 2002

The Game of Nim is played with several piles of objects. That the game starts with more than one pile is important. Since there is no limitation on how many objects can be removed on a move, Nim, on a single pile, is a bland, one move win for a first player. The situation changes when the rules of the games introduce limitations on available moves. For example, Scoring and the Subtraction games may be meaningfully played on a single pile. Scoring limits the size of a move from above. In the Subtraction games, the move is restricted to a finite set of alternatives.

One Pile is the most direct generalization of Scoring and the simplest of the Subtraction games. On each move a player is permitted to remove any number of objects bounded both from above and below. (In the applet, a move is performed by pressing one of the buttons located on the perimeter of the drawing area. The Min and Max attributes can be modified by clicking a little off their central line.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

The Grundy numbers for the various sizes of the pile are easily found with the Mex rule. For example, for Min = 3 and Max = 5, we get

Pile size		0		1		2		3		4		5		6		7		8		9		10		11		12		13		14		15		16		17		18		19		20
Grundy number		0		0		0		1		1		1		2		2		0		0		0		1		1		1		2		2		0		0		0		1		1

The P-positions correspond to the piles whose size S falls into the range 0≤ S mod (Min + Max) < Min.

There is a small body of literature that delves into the variations of One Pile in which Min = 1 while Max depends on the previous move. These are usually referred to as the Take-Away games. On the first move a player is allowed to remove any number of objects, but the whole pile. Assuming x is the size of a move -- the number of the removed objects -- let f(x) stand for the maximum number of objects that could be legally removed on the subsequent move. Different choices of the function f lead, in principle, to different games. The following applet implements three prototypical games corresponding to f(x) = x (No more than ...), f(x) = 2x-1 (Less than twice ...), and f(x) = 2x (No more than twice ...). (A. J. Schwenk gave a complete solution to the games with f nondecreasing and satisfying f(x) ≥ x.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Schwenk makes a case for the importance of the losing starting positions, i.e. the positions in which, all other factors equal, the second player has a winning strategy. In all games, the smallest losing position holds a single object. (The second player wins without lifting a finger. See, e.g. Russell.)

Let then H₁ = 1 and define the sequence H_k+1 = H_k + H_m, where m = min {j: f(H_j) H_k}. Since, in the very least, f(H_k) H_k, the definition does make sense.

The fact that the sequence {H_i} consists of losing starting positions stems from two assertions.

(1)

Any natural number N can be uniquely represented as the sum H_j₁ + H_j₂ + H_j₃ + ... + H_{j_k}, where, for i = 1, ..., k-1, f(H_{j_i}) < H_{j_i+1}

(1) leads to a game specific binary representation of the size of the pile - position in a game.

(2)

Unless the size N of the pile is one of H_{j_i}, there are k = /N/ > 1 1's in the representation of N. The winning strategy is to remove the number of objects corresponding to the rightmost 1.

Such a move reduces the number of units /N/ and also insures that the next move could not accomplish the same feat. Thus, if the game is played right, unit reduction is only possible on every other move. Unit reduction is the key to the ultimate success because the only integer N for which /N/ = 0 is 0, the desired outcome of the final and winning move. (For more details, see Take-Away Games.)

Let's now determine the sequence {H_j} for the three games. By definition, {H_j} is always increasing.

f(x) = x

H₁ = 1, H₂ = H₁ + H₁ = 2, H₃ = H₂ + H₂ = 4, and, since f(H_j-1) = H_j-1 < H_j, H_j+1 = H_j + H_j, in general. H_i = 2ⁱ.

f(x) = 2x - 1

H₁ = 1, H₂ = H₁ + H₁ = 2, H₃ = H₂ + H₂. By induction, if H_j = H_j-1 + H_j-1, then f(H_j-1) = H_j - 1 < H_j, so that H_j+1 = H_j + H_j.

A surprise! Here too, H_i = 2ⁱ.

f(x) = 2x

H₁ = 1, H₂ = H₁ + H₁ = 2, and, since 2x x + 1, for x 1, H₃ = H₂ + H₁, H₄ = H₃ + H₂. Now, by induction, if H_j = H_j-1 + H_j-2, then, on one hand, f(H_j-2) = 2H_j-2 < H_j-1 + H_j-2 = H_j. On the other hand, f(H_j-1) = 2H_j-1 > H_j-1 + H_j-2 = H_j. Therefore, f(H_j+1) = H_j + H_j-1, by definition.

H_i = F_i, i = 1, 2, ..., where F_i, i = 0, 1, 2, ... are the Fibonacci numbers 1, 1, 2, 3, 5, ... Which explains why the latter game is known as the Fibonacci Nim.

(1) is then a generalization of E. Zeckendorf's theorem. Zeckendorf has proved that every positive integer N has a unique expansion into the sum of distinct Fibonacci numbers that contains no two successive terms of the Fibonacci sequence. (Does not this contradict the well known identity, F_2n+1 = F_2n + F_2n-2 + ... + F₂ + F₀?)

Daykin showed that Zeckendorf's theorem gives in fact a characterization of the Fibonacci sequence: if {f_i} is a sequence such that any positive integer has a unique representation as the sum of f_i's with no two successive terms in the expansion, then {f_i} is necessarily increasing and f_i = F_i, for i > 0.

Similarly, if we assume that a sequence {h_i} is increasing and every positive integer has a unique representation (1) as the sum h_j₁ + h_j₂ + h_j₃ + ... + h_{j_k}, where, for i = 1, ..., k-1, f(h_{j_i}) < h_{j_i+1}, for a nondecreasing function f with f(x) ≥ x, then necessarily h_i = H_i, with H_i's defined as above.

The proof is left to the reader as a playful exercise.

References

D. E. Daykin, Representation of Natural Numbers As Sums of Generalized Fibonacci Numbers, J London Math Soc, 35 (1960), 143-160
B. Russell, In Praise of Idleness, Routledge, 1996
A. J. Schwenk, Take-Away Games, The Fibonacci Quarterly, v 8, no 3 (1970), 225-234

Fibonacci Numbers

Golden Ratio in Geometry

Generalized Converse of Zeckendorf's Theorem

We are given that every positive integer N can be uniquely represented as a sum h_j₁ + h_j₂ + h_j₃ + ... + h_{j_n}, where, for I = 1, ..., n-1, f(h_{j_i}) < h_{j_i+1}, for a nondecreasing function f with f(x) ≥ x.

We are to prove that, for k = 1, 2, ..., h_k+1 = h_k + h_m, where m = min{j: f(h_j)

h_k}.

If h_k+1 = h_k + h_m is not true, then either h_k+1 > h_k + h_m or h_k+1 < h_k + h_m.

The first of the inequalities is impossible, because then, taking N = h_k + h_m, we have h_k < N < h_k+1. Since the expansion of N is bound to end with h_k: N = h_k + h_j₁ + ... + h_{j_n}, we get h_m = h_j₁ + ... + h_{j_n}, in violation of the uniqueness of the expansion.

Assume then h_k+1 < h_k + h_m. Then h_k+1 > h_k + h_m-1. For, otherwise, h_k + h_m-1 would have an expansion that ends with h_k+1. Furthermore, from the choice of m, f(h_m-1) < h_k. We thus have

(4)

h_m-1 < h_k+1 - h_k < h_m.

As before, the expansion of h_k+1 - h_k is bound to include h_m-1:

h_k+1 - h_k = h_j₁ + ... + h_{j_n},

where f(h_{j_i}) < h_{j_i+1}, I = 1, ..., n-1, and h_{j_n} = h_{m - 1}. We therefore get the expansion (for f(h_m-1) < h_k)

h_k+1 = h_j₁ + ... + h_{j_n} + h_k,

which, too, contradicts the uniqueness assumption.

As we see, h_k+1 = h_k + h_m is the only possibility.

72111979