Chessboard decimation

Probability Level 2

You and a friend start with a standard 8x8 chessboard.

You play a game where each player takes turns removing an $n \times n$ square, $1 \leq n \leq 8$ . The person to remove the last square loses the game. Which player has a winning strategy?

The first player The second player

1 solution

Geoff Pilling
Jan 3, 2019

The first player simply removes a 7x7 square, guaranteeing a win.

I wonder though if this can be generalized for rectangular $m$ x $n$ boards... 🤔

This works on any sized board because the number of remaining squares is always odd, right?

Henry U - 2 years, 5 months ago

Yup! Rectangular shaped boards would be interesting though.

Geoff Pilling - 2 years, 5 months ago

For boards of size $1 \times n$ , the answer is obvious, $A$ wins for even $n$ and $B$ for odd $n$ .

If the board is $n \times (n-1)$ , then $A$ can remove an $(n-1) \times (n-1)$ square, leaving the above situation for $B$ . As we saw, for odd length, the second player – which is now $A$ – wins. So, for even $n$ , $A$ wins on the $n \times (n-1)$ board, but for odd $n$ , we can't say anything because $A$ wouldn't start as I said.

Henry U - 2 years, 5 months ago

Again, for an $n \times (n-1)$ board, $A$ could also take an $(n-2) \times (n-2)$ square that only touches one side of the board. Then, there would be $2(n-1)+(n-2)=3n-4$ squares left in a long line (not straight, but one line). For odd $3n-4$ , this strategie would guarantee a win for $A$ , and $3n-4$ is odd iff $n$ is odd. So $A$ also wins the $n \times (n-1)$ board for odd $n$ , therefore $A$ wins on every $n \times (n-1)$ board.

Henry U - 2 years, 5 months ago

Also, $B$ wins on a $4 \times 2$ board (found by testing every possible first move and $B$ 's responses).

This then means, that $A$ wins the $4 \times 6$ board by taking away an $4 \times 4$ square, leaving the above situation.

Henry U - 2 years, 5 months ago

And in general, if (and only if) $B$ wins on the $m \times n$ board ( $m > n$ ), then $A$ wins on the $m \times (m+n)$ board.

Henry U - 2 years, 5 months ago

@Henry U – And by symmetry, $A$ then also wins the $n \times (n+m)$ board.

Henry U - 2 years, 5 months ago

This is my table of winning positions so far.

$\begin{array}{cccccccccccc} &1&2&3&4&5&6&7&8&9&10&\cdots \\ 1&B&A&B&A&B&A&B&A&B&A \\ 2&A&A&A&B&B&A&A&&&& \\ 3&B&A&A&A&&&&&&& \\ 4&A&B&A&A&A&A&&&&& \\ 5&B&B& &A&A&A&A&&&& \\ 6&A&A& &A&A&A&A&&&& \\ 7&B&A& & &A&A&A&A&&& \\ 8&A& & & & & &A&A&A&& \\ 9&B& & & & & & &A&A&A \\ 10&A&&& & & & & &A&A \\ \vdots&&&&&&&&&&&\ddots \end{array}$

Henry U - 2 years, 5 months ago

Ah yes, I agree with this diagram plus I think 5x2 is a win for B as well... Other than that I'm guessing there aren't too many more wins for B other than 1xn for odd n (and maybe 9x2?) but I'll need to take a closer look...

Geoff Pilling - 2 years, 5 months ago

@Geoff Pilling – Thanks for testing this! It makes $5 \times 7$ and $2 \times 7$ also winning positions for $A$ , because $A$ can force a $2 \times 5$ -position by placing the first square and then getting this situation where $A$ wins.

Henry U - 2 years, 5 months ago

@Henry U – Yup... I agree!

Geoff Pilling - 2 years, 5 months ago

If m+n is even, and you can remove m-1*n-1 squares, this strategy still works. If m+n is odd, it doesn't.

Thomas Hurrell - 2 years, 5 months ago

Ah, but what about if you can only remove squares from a board that is originally rectangular?

Geoff Pilling - 2 years, 5 months ago

I thought the same thing! 😃

Sumant Chopde - 2 years, 5 months ago