Given an square table. Exactly one beetle sits in each cell of the table. At 12.00 all beetles creep to some neighboring cell (two cells are neighboring if they have the common side).
Find the greatest number of cells which can become empty (i.e. without beetles) if
a) ;
b) .
(Problem Committee of BMO 2011)
a) Answer: .
(Solution of A. Zhuk, O. Volod'ko.) Let's mark cells of the table as it is shown in Fig. 1. It is obvious that all beetles from the marked cells after their moves must occupy different cells. That is, at least cells will remain occupied, so at most cells can become empty. On the other hand, it is easy to see that after moves all beetles can occupy the marked cells, so the beetles can make at least empty cells.
b) Answer: .
As in a), solution follows from Fig. 2 with marked cells. So the answer is .
