# Take-Away Games

Like One Pile, the *Take-Away* games are played on a single pile of objects. On the first move a player is allowed to remove any number of objects, but the whole pile. On any subsequent move, a player is allowed to remove any number of objects bounded from above by a quantity that depends on the previous move.

The applet below implements three such games. In one, a player can remove *no more than* what his or her opponent removed on the previous move. In the second game, the condition changes to *less than twice* of the previous move. An in the third, it's *no more than twice* the previous move.

What if applet does not run? |

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

Copyright © 1996-2018 Alexander Bogomolny

## Theory of the Take-Away Games

Let's express the rules of the games in mathematical terms.

Let x be the size of a move -- the number of the removed objects. Let f(x) designate the maximum number of objects that can be removed legally on the subsequent move.

Then in the first (*no more than*) game, *less than twice*) game, *no more than twice*) game,

In each game, there exists a sequence of **losing starting positions** H_{1}, H_{2}, and so on. For example, in every game on a pile with a single object, the first player loses automatically. Therefore, _{1} = 1 always._{i}'s and the second player follows a certain winning strategy, the first player has no chance of winning. On the other hand, if the initial pile holds a number of objects different from any of H_{i}'s, the first player can move to the nearest H_{i} and find himself in the winning shoes of the second player of the previous example.

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*.

## Proof of (1)

Both existence of the representation and its uniquences are shown by induction.

### Existence

For N = 1, N = H_{1}. Assume any N < H_{k} can be represented as a sum of distinct H_{ji}'s with _{ji}) < H_{ji+1}_{k} ≤ N < H_{k+1}.

By definition, H_{k+1} = H_{k} + H_{m} with _{k} < H_{m} ≤ H_{k}. It then follows by induction that

N = H_{k} + (H_{j1} + ... + H_{jn}),
| ||

where f(H_{ji}) < H_{ji+1} for i = 1, 2, ..., n-1. To establish existence we need only show that _{jn}) < H_{k}._{jn}) ≥ H_{k}.

H_{k+1} = H_{k} + H_{m} ≤ H_{k} + H_{jn} ≤ N,
| ||

contradicting the choice of N.

### Uniqueness

Obviously, N = 1 has a unique representation. Assume that is also true for _{k};_{k} ≤ N < H_{k+1}.

Given a sum H_{j1} + ... + H_{jn}, f(H_{j1}) < H_{j2} implies

H_{j1} + H_{j2} < H_{j2+1}.
| ||

Further, f(H_{j2}) < H_{j3} implies

H_{j1} + H_{j2} + H_{j3} < H_{j3+1}.
| ||

...

f(H_{jn-1}) < H_{jn} implies

H_{j1} + H_{j2} + ... + H_{jn} < H_{jn+1}.
| ||

It thus follows that for _{k} ≤ N < H_{k+1},_{k}. If such an N has two representations, then so does _{k},

### The Losing Positions

Let N(k) denote the k-th position, i.e. the size of the pile after k moves. If /N(k)/ = 1 and the player can't remove all N(k) objects, then any move he does make permits his opponent to decrease /N(k+1)/.

Assume N(k) = H_{n1} for some n_{1}. Now, unless /N(k+1)/ = 1, the opponent may remove any number of objects corresponding to one of the binary units in the expansion of N(k+1), thus reducing /N(k+1)/. If, on the other hand, _{n2}_{2}< n_{1},_{n2}._{n2} ≤ H_{n1-1},

H_{n1} - H_{n2} ≥ H_{n1} - H_{n1-1} = H_{m}, where

m is the least among {j: f(H_{j}) ≥ H_{n1-1}}. Therefore,

f(H_{m}) ≥ H_{n1-1} ≥ H_{n2}.

### The Winning Startegy

Assume a game starts with N(0) objects, /N(0)/ > 1, so that N = H_{j1} + H_{j2} + ... + H_{jn} with _{j1}. Then, since _{j1}) < H_{j2},_{j2}. Therefore, any amount he removes will not effect the terms of the sum beyond H_{j2}. On the other hand, whatever quantity H_{j2} is replaced with, the former will contain at least one 1 in its expansion, such that the number of units in the expansion on that move would not be reduced.

If the game starts with N(0) objects, /N(0)/ = 1, the first player is bound to lose, because the second player will always be able to apply the strategy described in the previous paragraph.

### References

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

Copyright © 1996-2018 Alexander Bogomolny