Take-Away Games

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, f(x) = x. In the second (less than twice) game, f(x) = 2x - 1. Finally, in the third (no more than twice) game, f(x) = 2x.

In each game, there exists a sequence of losing starting positions H₁, H₂, and so on. For example, in every game on a pile with a single object, the first player loses automatically. Therefore, H₁ = 1 always. If a game starts with one of H_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 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) leads to a game specific binary representation of the size of the pile - position in a game.

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

Proof of (1)

Uniqueness

Obviously, N = 1 has a unique representation. Assume that is also true for N < H_k; and let H_k N < H_k+1.

Given a sum H_j1 + ... + H_jn, f(H_j1) < H_j2 implies

Further, f(H_j2) < H_j3 implies

...

f(H_jn-1) < H_jn implies

It thus follows that for H_k N < H_k+1, any representation of N is bound to include H_k. If such an N has two representations, then so does N - H_k, which violates the inductive assumption.

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₁. 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, /N(k+1)/ = 1, i.e. if N(k+1) = H_n2 for some n₂< n₁, the next player to win must be able to remove the whole of N(k+1) = H_n2. Indeed, H_n2 H_n1-1, so that

	Hn1 - Hn2 Hn1 - Hn1-1 = Hm, where

m is the least among {j: f(H_j) H_n1-1}. Therefore,

	f(Hm) Hn1-1 Hn2.

The Winning Startegy

Assume a game starts with N(0) objects, /N(0)/ > 1, so that N = H_j1 + H_j2 + ... + H_jn with n 2. Assume a player removes H_j1. Then, since f(H_j1) < H_j2, the next player can't remove even H_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