Yet another very fine puzzle from A Moscow Math Circle: Week by Week Problems by Sergey Dorichenko.
Each square of a 9 x 9 board has a bug sitting on it. On a signal, each bug crawls onto one of the squares which shares a side with the one the bug was on. (a) Prove that one of the squares is now empty. (b) Can the bugs move so that there would be exactly one empty square?
As always, please send your answers as comments within the blog (preferred), or send an e-mail to firstname.lastname@example.org. Please do share the puzzle with others if you like, and please also send puzzles that you have come across that you think I can share in this blog.
Mark the square black and white as in a chess board. Note that there are 41 black squares and 40 white squares.
a) Since in any operation, black ants move to white and white and moves to black, at least one black square remains empty.
b) In the 9×9 square, peel layer by layer. Each layet other than centre has an even length and can have a clockwise movement of bug. The centre but moved to step 2 and shares the place with some other bug thus making one spot empty but others in the right spot. Proof by construction.