Физтех 2024, отборочный этап, 9 класс, второй тур, задача 8
Клетки доски размером раскрасили в чёрный и белый цвета так, что среди любых двух клеток, имеющих общую сторону, есть хотя бы одна чёрная. Какое наименьшее количество чёрных клеток может быть на доске?
Ответ
Ответ. .
Решение. Отделим одну угловую клетку, а остальные клетки разобьём на пар соседних по стороне клеток. В каждой такой паре есть хотя бы одна чёрная клетка, поэтому чёрных клеток не меньше .
Пример с чёрными клетками получается при шахматной раскраске доски, в которой угловые клетки белые.