8
$\begingroup$

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?

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

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.

$\endgroup$

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.