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.


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.


What if applet does not run?

Some theory

[an error occurred while processing this directive]

[an error occurred while processing this directive]

|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, 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 H1, H2, and so on. For example, in every game on a pile with a single object, the first player loses automatically. Therefore, H1 = 1 always. If a game starts with one of Hi'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 Hi's, the first player can move to the nearest Hi and find himself in the winning shoes of the second player of the previous example.

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.

Proof of (1)

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

Existence

For N = 1, N = H1. Assume any N < Hk can be represented as a sum of distinct Hji's with f(Hji) < Hji+1; and let Hk ≤ N < Hk+1.

By definition, Hk+1 = Hk + Hm with m ≤ k. Therefore N - Hk < Hm ≤ Hk. It then follows by induction that

(3)
N = Hk + (Hj1 + ... + Hjn),

where f(Hji) < Hji+1 for i = 1, 2, ..., n-1. To establish existence we need only show that f(Hjn) < Hk. Assume to the contrary that f(Hjn) ≥ Hk. But then

Hk+1 = Hk + Hm ≤ Hk + Hjn ≤ N,

contradicting the choice of N.

Uniqueness

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

Given a sum Hj1 + ... + Hjn, f(Hj1) < Hj2 implies

Hj1 + Hj2 < Hj2+1.

Further, f(Hj2) < Hj3 implies

Hj1 + Hj2 + Hj3 < Hj3+1.

...

f(Hjn-1) < Hjn implies

Hj1 + Hj2 + ... + Hjn < Hjn+1.

It thus follows that for Hk ≤ N < Hk+1, any representation of N is bound to include Hk. If such an N has two representations, then so does N - Hk, 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) = Hn1 for some n1. 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) = Hn2 for some n2< n1, the next player to win must be able to remove the whole of N(k+1) = Hn2. Indeed, Hn2 ≤ Hn1-1, so that

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

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

f(Hm) ≥ Hn1-1 ≥ Hn2.

The Winning Startegy

Assume a game starts with N(0) objects, /N(0)/ > 1, so that N = Hj1 + Hj2 + ... + Hjn with n ≥ 2. Assume a player removes Hj1. Then, since f(Hj1) < Hj2, the next player can't remove even Hj2. Therefore, any amount he removes will not effect the terms of the sum beyond Hj2. On the other hand, whatever quantity Hj2 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

  1. A. J. Schwenk, Take-Away Games, The Fibonacci Quarterly, v 8, no 3 (1970), 225-234

[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]