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

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

решение

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

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