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? |
Fibonacci Numbers
- Ceva's Theorem: A Matter of Appreciation
- When the Counting Gets Tough, the Tough Count on Mathematics
- I. Sharygin's Problem of Criminal Ministers
- Single Pile Games
- Take-Away Games
- Number 8 Is Interesting
- Curry's Paradox
- A Problem in Checker-Jumping
- Fibonacci's Quickies
- Fibonacci Numbers in Equilateral Triangle
- Binet's Formula by Inducion
- Binet's Formula via Generating Functions
- Generating Functions from Recurrences
- Cassini's Identity
- Fibonacci Idendtities with Matrices
- GCD of Fibonacci Numbers
- Binet's Formula with Cosines
- Lame's Theorem - First Application of Fibonacci Numbers
|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,
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,
Let then H1 = 1 and define the sequence Hk+1 = Hk + Hm, where
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, | |
(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 | |
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 {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(x) = 2x - 1
H1 = 1, H2 = H1 + H1 = 2, H3 = H2 + H2. By induction, if
A surprise! Here too, Hi = 2i.
f(x) = 2x
H1 = 1, H2 = H1 + H1 = 2, and, since
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
By definition, Hk+1 = Hk + Hm with
| (3) | N = Hk + (Hj1 + ... + Hjn), | |
where f(Hji) < Hji+1 for i = 1, 2, ..., n-1. To establish existence we need only show that
| 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
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
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,
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
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
72202019