3
$\begingroup$

A game is played by two players on a $9\times 9$ board. At the beginning, one mark is placed on each square. As long as there are two marks on squares sharing a side, the first player picks one such pair of marks, and the second player chooses which mark to remove.

What is the maximum number of marks that the first player can remove, no matter how the second player plays?

The first player can remove $40$ marks by choosing non-overlapping pairs of marks. But it might be possible to remove more if she takes into account the second player's move, e.g. when a mark is removed, in the next turn choose a pair that contains the mark that is not removed from the last turn.

$\endgroup$
3
$\begingroup$

You can't get better than 40: Apply aa chess-board colouring with 41 black and 40 white squares. The first player will always pick a black and a white square and the second can always unmark a white square.

$\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.