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 adjacent squares (meaning squares sharing a side), the first player picks one mark with at least one other mark on an adjacent square, and the second player removes one of the marks on an adjacent square.

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

The first player can remove $40$ marks by repeatedly choosing all $41$ marks on "black cells" in chessboard coloring until all the remaining $40$ marks are removed. However, the argument used in a variant that $40$ is the best doesn't work here.

• Can you solve it for smaller boards, and see whether the solution scales up? Aug 12 '17 at 5:49
• The first player just chooses his mark or removes it?
– Aqua
Aug 12 '17 at 7:32
• The first player chooses a mark, the second player chooses an adjacent mark to remove.
– pi66
Aug 12 '17 at 13:22

The first player can force the second player to remove 81-21=60 marks. The second player can always remove at most 81-17=64. So the answer is somewhere in the range 60 to 64, but I don't know more precisely than that.

The first player can force the second player to remove all but 21 marks by picking the 17 red squares (drawn as circles) in the following artwork until they all have no adjacent marked square.

Here it is as text in case the image doesn't work. Red=* green=. blue=?.

.*..?.*..
...*....*
*....*...
..*....*.
?...*...?
.*....*..
...*....*
*....*...
..*.?..*.


The only remaining marks will be in the squares labelled red or blue, of which there are 21. (In graph theory terms, the red and blue vertices form an independent dominating set of order 21 in the 9x9 grid graph.)

The second player can use the strategy of "try to save the reds" to ensure 17 marks are left. In this strategy, whenever there is the option to do so, player 2 chooses a square that is not red. There is never a choice of which red square to spare: no square is adjacent to two red squares. The only way a red square can become unmarked is when player 1 chooses a marked neighbour of the red square such that the neighbour has no other marked neighbors. This implies that after unmarking the red square, that neighbour will have no marked neighbors at all and therefore will never be unmarked. So each of the 17 red squares ends up with a mark either on it or adjacent to it, and these 17 marks are all distinct.