Scoring Misère: Two Heaps Perfect Strategy
Misère games are played by the same rules as the normal ones with one notable exception: while in the normal game the player unable to move loses, in the misère games, the player unable to move wins.
In the Scoring misère, like in Scoring, the players are presented with one or more piles (or heaps) of objects (chips, counters, pebbles.) A move consists in removing a number of objects from a single pile. In Scoring (normal or misère), a player, on a single move, is allowed to remove one or more objects up to a prescribed maximum. In the misère game, the player who was forced to remove the last item loses.
Unlike the normal games, the misère does not in general have a perfect strategy. However, in case of just two heaps a perfect strategy does exists.
The MAA Math Horizons magazine (v 17, n 4, April 2010, pp. 31-33) posted a solution to the problem by Dan Kalman and Michael Keynes of American University which the called Double Take:
Starting with two non-empty stacks of chips, one of size m and the other of size n, the two players alternate turns and take 1, 2, or 3 chips from a single stack on each turn. The loser is the player who removes the last chip out of the initial
In the problem, the players are allowed to remove maximum of 3 chips. In the applet this restriction is removed and you can specify the maximum move of any size - in principle, of course. For technical reasons the applet allows to remove at most 10 chips. The chips are represented by small squares lined in a row (a heap). The squares are counted left to right. To remove a desired (but legal) number of squares click on the first one to be removed.
| What if applet does not run? |
References
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 2, A K Peters, 2003
- J. H. Conway, On Numbers And Games, A K Peters, 2001
- R. Guy, fair game, Comap's Explorations in Mathematics, 1989
|Contact| |Front page| |Contents| |Games|
Copyright © 1996-2018 Alexander Bogomolny
| What if applet does not run? |
The three correct submissions to the Math Horizons magazine proved that the second player wins just when one of the following is true (see modular arithmetic):
|
(a) m ≡ 0 (mod 4) and n ≡ 1 (mod 4), or vice versa, (b) m ≡ n ≡ 2 (mod 4), (c) m ≡n ≡ 3 (mod 4). |
More generally, if the largest allowed move is M ≥ 2 then, besides (a), the felicitous for the second starting positions are described as
|
(a') m ≡ 0 (mod M+1) and n ≡ 1 (mod M+1), or vice versa, (b') m ≡ n ≡ k (mod M+1), 2 < k ≤ M. |
The extension is quite straightforward and implicit in the submitted solutions which were based on the folowing observations:
|
The extension is obvious.
|Contact| |Front page| |Contents| |Games|
Copyright © 1996-2018 Alexander Bogomolny
72395923