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$
3
  • 1
    $\begingroup$ I'm assuming that your reflection is "point-reflection"... $\endgroup$
    – gebruiker
    Jul 27, 2017 at 12:52
  • 1
    $\begingroup$ yes, of course, I meant reflections through the central point $\endgroup$
    – tong_nor
    Jul 27, 2017 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, 2018 at 7:26

1 Answer 1

Reset to default
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$

You must log in to answer this question.

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