|
|
|
|
|
|
|
|
|
Take-Away GamesLike 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.
Copyright © 1996-2008 Alexander Bogomolny
Theory of the Take-Away GamesLet'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) 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 Let's now determine the sequence {Hj} for the three games. By definition, {Hj} is always increasing. f(x) = xH1 = 1, H2 = H1 + H1 = 2, H3 = H2 + H2 = 4, and, since f(x) = 2x - 1H1 = 1, H2 = H1 + H1 = 2, H3 = H2 + H2. By induction, if A surprise! Here too, Hi = 2i. f(x) = 2xH1 = 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. ExistenceFor 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
where f(Hji) < Hji+1 for i = 1, 2, ..., n-1. To establish existence we need only show that
contradicting the choice of N. UniquenessObviously, N = 1 has a unique representation. Assume that is also true for Given a sum Hj1 + ... + Hjn, f(Hj1) < Hj2 implies
Further, f(Hj2) < Hj3 implies
... f(Hjn-1) < Hjn implies
It thus follows that for The Losing PositionsLet 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,
m is the least among {j: f(Hj)
The Winning StartegyAssume 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
Copyright © 1996-2008 Alexander Bogomolny
|
Hk}.
N < Hk+1.| 28764178 |  |
|