 # 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 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 H1 = 1 and define the sequence Hk+1 = Hk + Hm, where m = min {j: f(Hj) Hk}. Since, in the very least, f(Hk) Hk, the definition does make sense.

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

 (1) Any natural number N can be uniquely represented as the sum Hj1 + Hj2 + Hj3 + ... + Hjk, where, for i = 1, ..., k-1, f(Hji) < Hji+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 Hji, 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 {Hj} for the three games. By definition, {Hj} is always increasing.

### f(x) = x

H1 = 1, H2 = H1 + H1 = 2, H3 = H2 + H2 = 4, and, since f(Hj-1) = Hj-1 < Hj, Hj+1 = Hj + Hj, in general. Hi = 2i.

### f(x) = 2x - 1

H1 = 1, H2 = H1 + H1 = 2, H3 = H2 + H2. By induction, if Hj = Hj-1 + Hj-1, then f(Hj-1) = Hj - 1 < Hj, so that Hj+1 = Hj + Hj.

A surprise! Here too, Hi = 2i.

### f(x) = 2x

H1 = 1, H2 = H1 + H1 = 2, and, since 2x x + 1, for x 1, H3 = H2 + H1, H4 = H3 + H2. Now, by induction, if Hj = Hj-1 + Hj-2, then, on one hand, f(Hj-2) = 2Hj-2 < Hj-1 + Hj-2 = Hj. On the other hand, f(Hj-1) = 2Hj-1 > Hj-1 + Hj-2 = Hj. Therefore, f(Hj+1) = Hj + Hj-1, by definition.

Hi = Fi, i = 1, 2, ..., where Fi, 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, F2n+1 = F2n + F2n-2 + ... + F2 + F0?)

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

Similarly, if we assume that a sequence {hi} is increasing and every positive integer has a unique representation (1) as the sum hj1 + hj2 + hj3 + ... + hjk, where, for i = 1, ..., k-1, f(hji) < hji+1, for a nondecreasing function f with f(x) ≥ x, then necessarily hi = Hi, with Hi's defined as above.

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

### References

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

We are given that every positive integer N can be uniquely represented as a sum hj1 + hj2 + hj3 + ... + hjn, where, for I = 1, ..., n-1, f(hji) < hji+1, for a nondecreasing function f with f(x) ≥ x.

We are to prove that, for k = 1, 2, ..., hk+1 = hk + hm, where m = min{j: f(hj) hk}.

If hk+1 = hk + hm is not true, then either hk+1 > hk + hm or hk+1 < hk + hm.

The first of the inequalities is impossible, because then, taking N = hk + hm, we have hk < N < hk+1. Since the expansion of N is bound to end with hk: N = hk + hj1 + ... + hjn, we get hm = hj1 + ... + hjn, in violation of the uniqueness of the expansion.

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

 (4) hm-1 < hk+1 - hk < hm.

As before, the expansion of hk+1 - hk is bound to include hm-1:

 hk+1 - hk = hj1 + ... + hjn,

where f(hji) < hji+1, I = 1, ..., n-1, and hjn = hm - 1. We therefore get the expansion (for f(hm-1) < hk)

 hk+1 = hj1 + ... + hjn + hk,

which, too, contradicts the uniqueness assumption.

As we see, hk+1 = hk + hm is the only possibility. 