# 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 game 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.)

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.

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.

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 proven 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

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. In September 2002 the site has welcomed its 5,000,000th visitor. Alex holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com