# coins on chessboard, who has the winning strategy

The game begins with empty $n\times n$ chessboard and a fixed number $m\in\{1,2,\dots,n\}$.

Two players are making moves alternately, each move is placing a coin on one empty square, each row and column can contain at most $m$ coins, the guy who cannot put a coin when he is to play, loses.

Who has the winning strategy?

In the original problem there was $n=2011$ and $m=1005$.

My solution:

The first guy wins. First move: a coin in the centre, then symetrical reflections of opponent's moves.

After solving the problem, I generalised it.

My above solution works for all $n,m$ both odd.

If $n$ is even, then the second guy wins by symetrical reflections.

What about remaining cases?

• I'm assuming that your reflection is "point-reflection"... – gebruiker Jul 27 '17 at 12:52
• yes, of course, I meant reflections through the central point – tong_nor Jul 27 '17 at 19:45
• This seems closely related to two-dimensional nim where every pile has size 1. But I am afraid that approach takes us nowhere. – Cyriac Antony Apr 12 '18 at 7:26

## 1 Answer

The remaining case is $n$ odd, $m$ even. My first intuition was the second player wins but my proof fails.

The maximum number of coins that can fit on a $n \times n$ chessboard without making a $m+1$-alignment is $n*m$, which is even.

If there are less than $n*m$ coins disposed, you can always find at least one row and one column with less than $m$ coins. If their intersection is free, you can play there. Alas we cannot be sure that this is the case, for instance with n=3, m=2:

| _ | _ | X |

| X | X | _ |

| X | X | _ |

Second player cannot play anymore.