задачка про жуков

М.Г. напомнила задачи из украинской математической олимпиады 89 года (по идее, я в ней тоже участвовал, но задачи не помню совсем).

Первая задача для 7 класса мне очень понравилась. Ее можно решить в уме (но необязательно, пользуйтесь бумагой, если в уме не получается). Я где-то полчаса сидел в кафе, уставившись в пространство. Задним умом кажется, что мог куда быстрее, но это всегда так.

*****
На каждой клетке доски размером 9x9 сидит жук. По сигналу одновременно каждый жук переползает в одну из соседних ПО ДИАГОНАЛИ клеток. При этом может оказаться, что в одних клетках соберется по несколько жуков, а другие наоборот будут свободными. Найдите наименьшее возможное количество свободных клеток.
*****

(я не буду скрывать комментарии, там могут быть правильные решения)