Задача 67296

Тема:    [ Подсчет двумя способами ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Френкин Б.Р.

В таблице $44\times 44$ часть клеток синие, а остальные красные. Никакие синие клетки не граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам (от любой красной клетки можно добраться до любой другой красной, переходя из клетки в клетку через общую сторону и не заходя в синие клетки). Докажите, что синих клеток в таблице меньше трети.

Решение

Положим $N=44$, и пусть $b$ и $r$ – количества синих и красных клеток. Оценим сверху количество $M$ общих сторон красных клеток с синими.

Всего у красных клеток $4r$ сторон, откуда $M\leqslant4r$. Вдоль краёв таблицы стоит не меньше $2N$ сторон красных клеток, поэтому $M\leqslant 4r-2N$. Теперь рассмотрим граф, вершины которого – красные клетки, а рёбра соединяют клетки, имеющие общую сторону. По условию граф связен, поэтому количество его рёбер не меньше $r-1$. Каждому из них отвечает общая сторона двух красных клеток, засчитанная в величине $4r$ два раза, поэтому из $M$ можно вычесть $2(r-1)$. Получаем $$M⩽4r-2N-2(r-1)=2r-2N+2.(1)$$

Оценим теперь $M$ снизу. Сложив количества сторон всех синих клеток, получим $4b$. Ясно, что на одной стороне таблицы не больше $N/2$ сторон синих клеток. Поэтому $$M⩾4b-2N.(2)$$

Из (1) и (2) следует, что $4b-2N\leqslant M\leqslant 2r-2N+2$. Поскольку $b+r=N^2$, получаем отсюда $6b\leqslant 2N^2+2$, или $$b⩽N^2/3+1/3.$$ Поскольку $N^2=44^2\equiv 1 \pmod 3$, а $b$ целое, получаем нужный результат.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
год/номер
Номер	44
Дата	2022/23
вариант
Вариант	устный тур
задача
Номер	3