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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Can you structure your question, because I don't reall understand the game. $\endgroup$– hlapointeNov 1, 2015 at 21:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
