Last stone game
 |
Last stone game is a game for two players with simple rules. As its name implies, the game was perhaps played with stones in the olden days. Though simple, the mathematics of the game is however interesting, intriguing and profound.
Introduction
How to play
It starts of by placing stones into three (3) or more groups, preferably with different numbers. The initial arrangement can be decided by either party. It will be seen that this is an important strategy of the game.
It can actually be played with two (2) groups of stones but the game will be too simple as demonstrated by a section herein under.
Each player then shall take turn to remove stones, from one and only one group of the stones. For the turn of each player, at least one stone shall be removed and the maximum removal allowed is the total remaining stones for that group.
Loser
The player who removes the last stone is the loser.
Playing with numbers
It is more convenient to play this game on a piece of paper by substituting the stones with numbers. It starts off with three (3) or more numbers written on the paper and each player takes turn to reduce one and only one number at a time.
Illustration
Move Player Move 0 (12, 4, 8) opening 1 A (2, 4, 8) 2 B (2, 4, 6) 3 A (2, 4, 5) 4 B (1, 4, 5) 5 A (1, 3, 5) 6 B (1, 3, 2) 7 A (1, 2, 2) 8 B ( 2, 2) 9 A ( 1, 2) 10 B ( 1) 11 A (0) Player A removes the last stone. He loses.
History of the game
(anybody has knowledge of the early history of the game?)
The game is often played by students. The game can also be found in Casio manual as a programme for Casio 601 (?) calculator. The name of the game is adopted from this manual.
Trick for a set of two numbers
If Player A reduces the number set to (2, 2), there are two choices:
- Player B can make it (1, 2) and Player A will make it (1).
- Player B can make it (2) and Player A will make it (1) also.
That is to say for either choice Player B loses the game.
Now the winning strategy is for Player A to find, (x, y), such that:
- Condition 1.1: The number set is larger than (2, 2).
- Condition 1.2: Player B cannot reduce the number set (x, y) to a winning move such as (2, 2), (1), i.e. (x, y) shall not have either number to be 1 or 2.
- Condition 1.3: It is the smallest number set satisfying the above two conditions. If it is not the smallest number set then Player B will have a chance of making a move such that the resulting number set still satisfies the above two conditions.
Then naturally after Player B’s move with (x, y), Player A has the chance to reduce the number to winning moves such as (1) or (2, 2).
For example if (x, y) is (4, 2) then Player B can reduce to (2, 2) and Player A loses the game.
It is deduced that (x, y) shall be (3, 3), which satisfies all above conditions. If Player A makes the number set to be (3, 3), the following explores all possible moves of Player B:
Moves of Player B Moves of Player A Who Win (2, 3) (2, 2) Player A (2, 1) (1) Player A (2) (1) Player A
It has therefore been demonstrated that (3, 3) is a winning move for Player A if he can achieve this number set.
By the same deduction method, similar conditions can be set to deduce a winning number set larger than (3, 3). It can be therefore induced that the following are winning moves in addition to (2, 2) and (3, 3):
- (4, 4)
- (5, 5)
Trick for a set of three numbers
If Player A reduces the number set to (1, 1, 1), Player B loses the game. If Player A reduces the number set to (2, 2), Player B also loses the game as demonstrated earlier.
Now the winning strategy is for Player A to find (x, y, z), such that:
- Condition 2.1: The number set is larger than either (2, 2) or (1, 1, 1).
- Condition 2.2: Player B does not have a chance of reducing the number set to a winning number such as (2, 2) or (1, 1, 1), i.e. (x, y, z) shall not have two numbers identical with either sets of (1, 1, 1) or (2, 2). For example if (x, y, z) is (1, 2, 2) then Player B can reduce to (2, 2) and Player A loses the game.
- Condition 2.3: It is the smallest number set satisfying the above two conditions.
Then naturally after Player B’s move on (x, y, z), Player A has the chance to reduce the number to winning moves such as (1), (2, 2) or (1, 1, 1).
It is deduced that (x, y, z) shall be (1, 2, 3), which satisfies the above three (3) conditions. If Player A’s move is (1, 2, 3), the following explores all possible moves of Player B:
Moves of Player B Moves of Player A Who Win (1, 2, 2) (2, 2) Player A (1, 2, 1) (1, 1, 1) Player A (1, 2) (1) Player A (1, 1, 3) (1, 1, 1) Player A (1, 3) (1) Player A (2, 3) (2, 2) Player A
It has therefore been demonstrated that (1, 2, 3) is a winning move for Player A.
By the same deduction method, similar conditions can be set to deduce a winning number set larger than (1, 2, 3). It can be therefore induced that the following are also winning moves:
- (1, 4, 5)
- (1, 6, 7)
- (1, 8, 9)
Summary of winning move patterns
Fairly speaking, the game shall be classified as an unfair game or a trick. A player who knows the game can set up the trick such that his opponent has lost from the start.
The trick is to remember the winning moves (number sets) below. To win the game, a player shall make the number set confirming to them. Restricted by reducing only one number at a time, his opponent will not have chance to bring the number set confirming to a smaller winning moves.
- (2, 2)
- (3, 3)
- (4, 4)
- (5, 5)
- ...
- (n, n); where n is greater than 2
Or
- (1, 1, 1)
Or
- (1, 2, 3)
- (1, 4, 5)
- (1, 6, 7)
- (1, 8, 9)
- ...
- (1, 2n, 2n + 1); where n is any whole number not smaller than 1
It is also here quoted without proof that the following number sets are also winning moves:
- (2, 0, 2)
- (2, 1, 3)
- (2, 4, 6)
- (2, 5, 7)
- (2, 8, 10)
- (2, 9, 11)
- ...
- (2, 4n, 4n+2)
- (2, 4n+1, 4n+3)
Where n is any whole number not smaller than 0. Please note that the first two rows are repeated from smaller number sets above to show the pattern. The pattern can be derived simply from such arrangement.
The list can go on.
Last move game
Last move game is played with the same rule with a small but important variation as oppose to the last stone game:
- The player who makes the last move is the winner.
In the last stone game, the loser is forced to remove the last stone as that is the last stone left at his turn; whereas in the last move game, the winner will remove all stones in the last remaining group to win the game.
Winning strategy
Surprisingly, the change in the rule does not make significant change the wining moves.
Now with the new rule, if Player A reduces the number set to (1, 1) or (2, 2), Player B loses the game. Given the number set (2, 2), there are two choices for B:
- Player B can make it (1, 2) and Player A will make it (1, 1).
- Player B can make it (2) and Player A will make it (0).
For both choices, Player A wins the game. These number sets (1, 1) or (2, 2) are thus the basic winning number sets not dissimilar to (1, 1, 1) and (2, 2) for last stone game.
It can be deduced that the next wining number set is also (1, 2, 3).
In general all wining moves for last stone game are the wining moves for last move game except that (1, 1) replaces (1, 1, 1).
Ideal mathematical formula
Last move game is introduced by Ling Kah Jai. The winning moves of this game can be ideally formulated as a theory when (1, 1) replace (1, 1, 1) as a winning move. This will be shown in the next section.
Theory of winning formula
Having illustrated some of the winning tricks, the following quotes a theory by Ling Kah Jai on the winning formula for last move game played with a set of three (3) numbers (x, y, z).
- Theory: If x xor y xor z = 0, then (x, y, z) is a winning move. If a number set is not a winning move then it is a losing move, i.e. the opponent has a chance to reduce it to a winning move.
xor means bitwise eXclusive OR operator (exclusive disjunction) which is explained in its own Wiki page. To carry out the mathematical evaluation, it will be easier to convert all numbers to binary numbers for performing bitwise operation.
- x xor y xor z = 0 ⇔ z = x xor y
- x xor y xor z is also represented as xor(x, y, z) here.
For example, (4, 11, 15) is (100, 1011, 1111)2
- 100 xor 1011 = 1111; therefore (4, 11, 15) is one of the winning move.
- (3, 5, 7) is (11, 101, 111)2
- 11 xor 101 = 110 <> 111; therefore (3, 5, 7) is one not a winning but losing move.
It shall be noted that the quoted patterns of winning numbers in the previous section satisfy the theory.
The theory can be extended to a set of four or more numbers:
- If xor(a, b, c, d) = 0 then (a, b, c, d) is a winning move.
- If xor(a, b, c, d, e) = 0 then (a, b, c, d, e) is a winning move.
Thus the trick of winning the game is to reduce a number in the set such that the new number set conforms to the winning move.
Proof of the theory of winning formula
A set of two numbers such that x xor y = 0, i.e. x = y has been proven to be winning moves in one of the section above.
To prove the theory of winning formula, it is necessary to prove the following theories:
- Theory 1: If xor(A, B, C) = 0 and one and only one of its numbers is reduced and the number set becomes (A', B', C'), then xor(A', B', C') > 0;
- Theory 2: If xor(A', B', C') > 0, then it is possible to reduce one of its numbers such that the number set becomes (A", B", C") and xor(A", B", C") = 0.
Proof of Theory 1
- xor(A, B, C) = 0 ... (Condition 1)
- i.e. A = B xor C ... (Eqn 2)
- and B = A xor C ... (Eqn 3)
- and C = A xor B ... (Eqn 4)
The LHS of (Eqn 1) i.e. B xor C results in a unique solution A. If A is reduced, (Eqn 1) is no more true and thus Condition 1 will no more be true. By similar reasoning, if B or C is disturbed at a time, Condition 1 will also be upset and the proof is complete.
Proof of Theory 2
To prove Theory 2, it is necessary to prove in two parts:
- Theory 2a: If the numbers in the set (A', B', C') are identical, i.e. A' = B' = C' , Theory 2 holds.
- Theory 2b: If the numbers in the set (A', B', C') are not identical, Theory 2 also holds.
Proof of Theory 2a
xor(A', A', A') = (A' xor A') xor A' = A' , satisfy the condition of greater than zero.
The number set (A', A', A') can be reduced to (A', A' ) which is a wining move and thus complete the prove.
Proof of Theory 2b
To prove Theory 2b, it is necessary to prove the following:
- Theory 2c: If xor(A', B', C') > 0, then there exists one and only one a' such that: a' > b' xor c' ; where a' can be either A' , B' or C' ; and b' and c' are the remaining two numbers.
It is assumed that:
- xor(A', B', C') = D'
Operation (… and D') is called a masking function which is often used in computer programming, thus if D' = 11002.
(A' and 1100) means the 3rd and 4th bits (counting from the right) of A' shall remains whereas all other (insignificant) bits shall be replaced by zeros.
- xor(A', B', C') = D'
- ⇒ xor(A' and D', B' and D', C' and D') = (D' and D') = D'
- ⇒ xor(Ar', Br', Cr') = D' ; where "Ar' = (A' and D')etc.
Expressed in another manner:
- Ar' xor Br' xor Cr' = D' > 0
If ar' is the largest number among (Ar', Br', Cr') then
- ar' > br' xor cr';
ar' can thus be reduced to ar" such that:
- ar" = br' xor cr'
Thus
- (A' and D') > (B' and D') xor (C' and D') and A' can be reduced to A" such that:
- (A" and D') = (B' and D') xor (C' and D'); and
- A" = B' xor C'
This completes the proof for Theories 2c and 2b and thus Theory 2.
Proof of the winning theory
Given that Player 2 starts with the number set (A, B, C) such that xor(A, B, C) = 0, Player 2 cannot make a move such that the resultant number set is (A', B', C') and xor(A', B', C') = 0 according to Theory 1.
However, after his move, Player 1 can revert the situation and can always make a move to (A", B", C") such that xor(A", B", C") = 0 according to Theory 2.
Thus by mathematical induction, if winning moves of (A, B, C) with small numbers satisfy xor(A, B, C) = 0 , then all such possible (A, B, C) satisfying xor(A, B, C) = 0 are winning moves. The number sets (0, 1, 1), (0, 2, 2) and (0, n, n) etc are indeed winning moves. This completes the proof.
Other Variation of the game
Another variation to last stone game and last move game is restricting the maximum number of stones to be removed at each turn. This variation however simplifies the game to a very simple arithmetic and will not be illustrated here.