1
$\begingroup$

Given a square table $n\times n$, two players $A$ and $B$ are playing the following game: At the beginning all cells of the table are empty, and the players alternate playing with coins. Player $A$ has the first move, and in each of the moves a player will put a coin on some of the cells that doesn't contain a coin and is not adjacent to any of the cells that already contains a coin. The player who makes the last move is the winner. Which player has a winning strategy and what is the strategy?

Remark. The cells are adjacent if they share an edge.

The way the question is worded I assume that the same player will have the winning strategy regardless of the size of the $n\times n$ board. But this doesn't make sense because if we look at the simplest cases, for a $1 \times 1$ board the first player will always win, for a $2 \times 2$ board the second player will always win, for a $3 \times 3$ board the first player has the winning strategy, the strategy here is that player one will always win unless his in his first move he places a coin in a cell with exactly three adjacent coins.

I wasn't able to find the winning strategy for a $4 \times 4$ board yet but just from trying a few examples it looked like player 2 has the winning strategy so it looks like if $n$ is odd player 1 has the winning strategy and if $n$ is even then player 2 has the winning strategy.

Is this correct and how can I figure out a winning strategy? I tried to look at the number of open cells the player with the winning strategy should leave open at the end of their turn but I could not find a pattern there.

$\endgroup$
1
$\begingroup$

Solution (missing some details):

If $n$ is even, then the second player mirrors the moves of the first (with respect to the center of the table) and wins. Note that if the first player move is legal, then the second player's move is also legal.

If $n$ is odd, then the first player plays first in the middle of the board, then mirrors the moves of the second player with respect to the center of the board and wins.

$\endgroup$
  • $\begingroup$ I understand your reasoning, just making sure that the second part is "if $n$ is odd, then the first player plays in the middle of the board..." $\endgroup$ – idknuttin Nov 29 '16 at 2:58
  • 1
    $\begingroup$ After the first move in the middle of the board, the symmetry is assured, so the first player can always immitate the second symmetrically from the center of the board. So if $n$ is odd the first player has a winning strategy, while if $n$ is even the second player has a winning strategy. $\endgroup$ – Momo Nov 29 '16 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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