4
$\begingroup$

The fields of a table 1 x n are labeled 1, 2,...,n. A coin is placed on each of the fields n - 2, n -1, n. Two players play a game in which they alternately move a coin from a field j to an unoccupied field i, such that i < j. The game is lost for the player who cannot move a coin anymore.

Does the player who starts the game have the winning strategy? Please Prove it.

I'm trying to approach this question from simple cases. Like when n=3, the first mover(let's call it A as apposed to B) lose. When n = 4, A wins by moving coin form 4 to 1. When n=5, A wins by moving coin from 3 to 1. When n=6, A wins by moving coin from 6 to 1. so I guess maybe when n>1 it's always A winning. But I can't really see a pattern for generalized cases.

Improve this question
$\endgroup$
3
  • $\begingroup$ Very similar in spirit to this recent question: puzzling.stackexchange.com/questions/128810/… $\endgroup$
    – Nautilus
    Commented Oct 29 at 11:59
  • $\begingroup$ @Nautilus Yeah the problems seem similar. But that one is related to nim and I can't see how this one is related with nim. $\endgroup$
    – Susanna
    Commented Oct 29 at 12:19
  • $\begingroup$ Consider the distance of the coins from the first cell. The only difference is that the distances can't be the same. $\endgroup$
    – Nautilus
    Commented Oct 29 at 15:21

1 Answer 1

Reset to default
4
$\begingroup$

As starting player we can always move one coin to field 1 in our first move. Thus effectively taking this coin out of the game, so we only have to consider the remaining two coins. But which one to move?

After moving the first coin you want the other two coin in neighbouring fields, so that the lower one is an even position.
So if n is even move the coin from n to 1 (n-2 is also even, n-1 is odd), if n is odd move the coin from n-2 to 1 (n-1 is even, n is odd).
Whenever B moves a coin we move the other to a neighbouring position, so that the lower one stays even: If B moves a coin to an even postition p we move the other coin to p+1. If B moves a coin to an odd postition p we move the other coin to p-1.
This will eventually lead to the situation that we make the last move where the coins end in the positions 1,2,3 and B can't move.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You seem to assume that moving a coin to 1 is mandatory for a win. Note that though that is the obvious move, half the time moving n-1 to 2 (also) wins. $\endgroup$
    – Retudin
    Commented Oct 29 at 9:24
  • 1
    $\begingroup$ @Retudin that doesn't invalidate this answer, right? Establishing one winning strategy is enough. $\endgroup$
    – justhalf
    Commented Oct 29 at 13:33
  • 1
    $\begingroup$ Indeed, a perfectly OK solution. However, i.m.o. it would have been a bit more complete (and 'thus' more useful to other solvers) if it was explicitly mentioned that a path was chosen that was sufficient since it led to an answer. (and therefor I made a comment and not a separate answer) $\endgroup$
    – Retudin
    Commented Oct 29 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.