5
$\begingroup$


I was reading about different variations of nim game and I'm trying to find the winning strategy in one of them: there are n empty places on the circle. Two players are placing their coins on empty places. They can put their coin only on empty places which aren't next to a coin of the opponent. In one turn each player can place only one coin. The player who can't move loses. Who's got the winning strategy for each n?
I think that for even n the second player will win, because he can always place his coins symmetrically to the first player's. But what about for odd n?

$\endgroup$
1
  • $\begingroup$ Can you structure your question, because I don't reall understand the game. $\endgroup$
    – hlapointe
    Commented Nov 1, 2015 at 21:33

1 Answer 1

3
$\begingroup$

The first person will always win for odd $n$.

Your logic for why the second person will always win for even $n$ is correct. Now consider two players, Al and Bob, who are playing with odd $n$. Al makes the first move. Now, the game is the same as if Bob was making the first move in a game with even $n$, with the added restriction that he can't make his move next to where Al already has a coin. No matter what Bob does, Al can just pretend Al's the second player in a game with even $n$ and mirror Bob's moves, and so Al will always win with odd $n$. This is no problem because there's an added restriction to Bob, not to Al, and so Al will always be able to mirror Bob's moves.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .