Two people play the following game, starting with three piles of matches. In a turn,a player moves any positive number of matches from one of the piles to a larger pile.The player who can’t make a move loses (the player who makes the last move wins).
For example, in the position 17–12–12 you can move any number of matches from
either of the piles of 12 to the pile of 17, but these are the only possible moves. In the position 9–6–3 you can move matches from the 3-pile to either of the other piles,and from the 6-pile to the 9-pile.
Any hints for that problem? I have no idea where to start from !!
Best Answer
HINTS
Start at the end: what would be the end of this game?
I see 3 possibilities:
A. there is 1 pile left
B. There are 2 piles left with an equal amount of matches
C. There are 3 piles left with an equal amount of matches
Of course, as a player, I want to AVOID getting caught in any of these game 'states'.
Now ask: how can we get to these positions?
For A: there were 2 piles of different size and the smaller one, and the smaller one gets added to the bigger one
For B: I can't get there from 2 earlier piles, so I must have gotten to B from 3 piles of sizes $k$, $m$, and $k + m$, and where $k <m$ so that the pile of k matches could be added to the pile with $m$ matches
For C: This state can only happen if we started that way! (so make note of this as a very special case ... but otherwise there is no need to further consider this)
Now note that as a player, I WANT to be in any of the states that allow me to make the move to get to A or B respectively, because that means that my opponent will then lose. So, I have as WANT states:
Pre-A: Any two piles of different sizes
Pre-B: Any 3 piles of sizes $k$, $m$, and $k + m$, and where $k <m$
(of course, when I am in Pre-A or Pre-B I can do moves other than the one that gets me to A or B, but a perfect player will make the move to go to A or B respectively, so they will win the game)
OK, so now we want to figure out how to get to Pre-A and Pre-B respectively. What are those kinds of states? And: as a player, I want to AVOID those states, because if my opponent is a perfect player, I will lose.
Etc.... (it'll be a bit of work)
Good luck!