On each unit square of a $9 \times 9$ square, there is a bettle. Simultaneously, at the whistle, each bettle moves from its unit square to another one which has only a common vertex with the original one (thus in diagonal). Some bettles can go to the same unit square. Determine the minimum number of empty unit squares after the moves. Pierre.
Problem
Source: Me
Tags: analytic geometry
grobber
21.12.2004 19:37
I promise I won't spoil any more of these, but this problem is too cute : Give the squares coordinates: from $(1,1)$ to $(9,9)$. The squares with both coordinates odd can only be occupied by beetles from squares with both coordinates even. There are $21$ squares with both coordinates odd and $12=21-9$ squares with both coordinates even, meaning that at least $9$ squares remain empty. It's very easy to find a set of movements leaving exactly $9$ squares empty, so the answer is $9$.
rcv
26.12.2004 14:58
Here is a solution from a 12-year old student...
Instead of counting the empty squares, let's count the squares that have two bugs.
Begin by coloring the 9x9 square like a checkerboard, with black squares in the corners. Bugs on white squares have to stay on white squares. Bugs on black squares have to stay on black squares.
The bugs on the white squares can find a place where they don't share a square. (She demonstrated two proofs of this fact.) Now, she considered the black squares.
First, the bugs at the corners have only one place to move. Remember these four squares are occupied. Now, look at the left columns of bugs. There are still 3 bugs in the left column, but there are only 2 empty squares in the second column. No matter what they do, two bugs will have to share a square. Do the same for all four sides. We have at least 4 squares occupied by two bugs.
Do the same thing with what's left [meaning the 5x5 square, since the second column from the left, second row from the top, second row from the right, and second row from the bottom are all full of bugs.] The bugs in the corners [of the 5x5 square] have only one (empty) place to move (they move toward the center). This leaves the other bug in the third column with no (empty) place to move. Do the same for all four sides. We have 4 more squares occupied by two bugs.
Next, look at the middle square. This poor bug has to move to a square that's already full.
The answer is 9.
This was a very nice little problem, Pierre!
pbornsztein
26.12.2004 15:09
Thanks you. I agree. But, unfortunately, I'm not the creator of it. I just proposed it here from our pre-TST. Pierre.
Myth
26.12.2004 16:12
It is an old russian problem.
kueh
22.01.2005 14:13
colouring in 4 colours makes the solution show up easily (its equivalent to all other solutions here actually)