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

The Grundy numbers for the various sizes of the pile are easily found with the Mex rule. For example, for

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

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 *No more than ...*), *Less than twice ...*), and *No more than twice ...*). (A. J. Schwenk gave a complete solution to the games with f nondecreasing and satisfying

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} = 1 and define the sequence H_{k+1} = H_{k} + H_{m}, where _{j}) H_{k}}._{k}) H_{k},

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_{j1} + H_{j2} + H_{j3} + ... + H_{jk}, where, for i = 1, ..., k-1, _{ji}) < H_{ji+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_{ji}, there are | |

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

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

### f(x) = x

H_{1} = 1, H_{2} = H_{1} + H_{1} = 2, H_{3} = H_{2} + H_{2} = 4, and, since _{j-1}) = H_{j-1} < H_{j},_{j+1} = H_{j} + H_{j}, in general. H_{i} = 2^{i}.

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

H_{1} = 1, H_{2} = H_{1} + H_{1} = 2, H_{3} = H_{2} + H_{2}. By induction, if _{j} = H_{j-1} + H_{j-1},_{j-1}) = H_{j} - 1 < H_{j},_{j+1} = H_{j} + H_{j}.

A surprise! Here too, H_{i} = 2^{i}.

### f(x) = 2x

H_{1} = 1, H_{2} = H_{1} + H_{1} = 2, and, since _{3} = H_{2} + H_{1}, H_{4} = H_{3} + H_{2}. Now, by induction, if _{j} = H_{j-1} + H_{j-2},_{j-2}) = 2H_{j-2} < H_{j-1} + H_{j-2} = H_{j}._{j-1}) = 2H_{j-1} > H_{j-1} + H_{j-2} = H_{j}._{j+1}) = H_{j} + H_{j-1},

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, _{2n+1} = F_{2n} + F_{2n-2} + ... + F_{2} + F_{0}?)

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 _{i} = F_{i},

Similarly, if we assume that a sequence {h_{i}} is increasing and every positive integer has a unique representation (1) as the sum _{j1} + h_{j2} + h_{j3} + ... + h_{jk}_{ji}) < h_{ji+1}_{i} = H_{i},_{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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

### Generalized Converse of Zeckendorf's Theorem

We are given that every positive integer N can be uniquely represented as a sum _{j1} + h_{j2} + h_{j3} + ... + h_{jn}_{ji}) < h_{ji+1}

_{k+1}= h

_{k}+ h

_{m},

_{j}) h

_{k}}.

If _{k+1} = h_{k} + h_{m} is not true, then either _{k+1} > h_{k} + h_{m}_{k+1} < h_{k} + h_{m}.

_{k} + h_{m},_{k} < N < _{k+1}_{k}: _{k} + h_{j1} + ... + h_{jn},_{m} = h_{j1} + ... + h_{jn},

Assume then h_{k+1} < h_{k} + h_{m}. Then _{k+1} > h_{k} + h_{m-1}._{k} + h_{m-1}_{k+1}. Furthermore, from the choice of m, _{m-1}) < h_{k}.

(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_{j1} + ... + h_{jn},
| ||

where f(h_{ji}) < h_{ji+1}, I = 1, ..., n-1, and _{jn} = h_{m - 1}._{m-1}) < h_{k})

h_{k+1} = h_{j1} + ... + h_{jn} + h_{k},
| ||

which, too, contradicts the uniqueness assumption.

As we see, h_{k+1} = h_{k} + h_{m} is the only possibility.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny