A beetle on each square of a $9 \times 9$ chessboard. Each beetle crawls one square diagonally, find minimal possible no. of free squares.

Question

Question:

A beetle sits on each square of a $9 \times 9$ board. At a signal each beetle crawls diagonally onto a neighboring square. Then it may happen that several beetles will sit on the same square and none on others. Find the minimal possible number of free squares.
A free square is a square not occupied by any beetle.

What I did:

Colour each row black and white alternatively. Then 45 black and 36 white squares. Each beetle changes its colour, so the answer is at least 9.

The given answer is indeed 9, however, I am not able to construct such a case. Please help.

I do not know the source as it was in a PPT given by a teacher. However, I found this same question online, without an answer.

Answer 1

SUMMARY :

When we have $(2n) \times (2n)$ Board , all Beetles can make "Pairs" & exchange places. Hence no Square may be free.

When we have $(2n+1) \times (2n+1)$ Board , minimum $(2n+1)$ Squares may be free.

Proof 1:

Consider the $3 \times 3$ Board.
The Purple Beetles can easily make "Pairs" Diagonally. Alternately , the Purple Beetles can move around cyclically.
All the Blue Beetles in the Corners can move to Center , while the Center Blue Beetle can move to top left corner , hence $3$ Squares (right-most & bottom-most) will be free.

Consider $5 \times 5$ Board.
The Blue Beetle in the top left corner can move down & that Blue Beetle can move to the top left corner.
Similarly , every Blue Beetle (except the last Column) in top row can move downwards & the Blue Beetle can move upwards.
Similarly the third row (except the last Column) & fourth row can exchange.

That leaves the right-most & the bottom-most Blue Beetles (Green Circles) , who must move to occupied Squares , leaving $5$ Squares free.

Same way , $7 \times 7$ Board will leave $7$ Squares free.
Like-wise , $9 \times 9$ Board will leave $9$ Squares free : the right-most & the bottom-most.
Hence , $(2n+1) \times (2n+1)$ Board will leave $(2n+1)$ Squares free : the right-most & the bottom-most.

Proof 2:

Since the Purple Beetles can always make "Pairs" & exchange places or move in cycles , we have to consider only the Blue Beetles.
The $(2n+1) \times (2n+1)$ Board will have a $(2n) \times (2n)$ Board when we leave out the rightmost Column & the bottom-most row.
That $(2n) \times (2n)$ Board can always ensure no free Squares.

Hence the rightmost Column & the bottom-most row will have to move away to leave $2n+1$ free Squares.

Answer 2

Let us colour the Board with a $2 \times 2$ Pattern having $4$ colours.

Suppose the top left square is coloured red, and the one to its right is coloured blue. The square below red is green and the square below blue is yellow. Now, for every red square, colour all its diagonal neighbours yellow, and vice-versa. Same for blue and green.

Now, we observe that a beetle moves from red to yellow (or vice-versa) or blue to green (or vice-versa). There are 20 blue, 20 green, 16 yellow and 25 red squares.

One such possible construction is:
Since there are equal no. of blues and greens in a diagonal, one can pair adjacent squares on such a diagonal, and swap beetles within a pair. As for the diagonals containing red and yellow, we can move each beetle southeast. In the last row and last column, there are some beetles on red squares which can't move, so we move them to any adjacent yellow square.

In the end, the only free squares are the red squares in the first row and first column, total 9.