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

Покрасьте вертикали доски в чёрный и белый цвет через одну. Тогда с чёрной клетки жук переползает на белую, а с белой - на чёрную.

Решение

Покрасим вертикали доски в чёрный и белый цвет через одну. В результате в чёрный цвет будет покрашено 5*9 = 45 клеток (5 вертикалей), а в белый - только 36. Заметим, что с чёрной клетки жук может переползти только на белую, а белой - только на чёрную. Следовательно, после того, как жуки переползли в соседние по диагонали клетки, на 45 чёрных клетках оказалось 36 жуков. Значит, по крайней мере 9 чёрных клеток оказались незанятыми.

Покрасим вертикали доски в чёрный и белый цвет через одну. В результате в чёрный цвет будет покрашено 5*9 = 45 клеток (5 вертикалей), а в белый - только 36. Заметим, что с чёрной клетки жук может переползти только на белую, а белой - только на чёрную. Следовательно, после того, как жуки переползли в соседние по диагонали клетки, на 45 чёрных клетках оказалось 36 жуков. Значит, по крайней мере 9 чёрных клеток оказались незанятыми.