|
|
 |
Условие
В таблице $44\times 44$ часть клеток синие, а остальные красные. Никакие синие клетки не граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам (от любой красной клетки можно добраться до любой другой красной, переходя из клетки в клетку через общую сторону и не заходя в синие клетки). Докажите, что синих клеток в таблице меньше трети.Решение
Положим $N=44$, и пусть $b$ и $r$ – количества синих и красных клеток. Оценим сверху количество $M$ общих сторон красных клеток с синими.Всего у красных клеток $4r$ сторон, откуда $M\leqslant4r$. Вдоль краёв таблицы стоит не меньше $2N$ сторон красных клеток, поэтому $M\leqslant 4r-2N$. Теперь рассмотрим граф, вершины которого – красные клетки, а рёбра соединяют клетки, имеющие общую сторону. По условию граф связен, поэтому количество его рёбер не меньше $r-1$. Каждому из них отвечает общая сторона двух красных клеток, засчитанная в величине $4r$ два раза, поэтому из $M$ можно вычесть $2(r-1)$. Получаем $$M\leqslant4r-2N-2(r-1)=2r-2N+2. \quad (1) $$
Оценим теперь $M$ снизу. Сложив количества сторон всех синих клеток, получим $4b$. Ясно, что на одной стороне таблицы не больше $N/2$ сторон синих клеток. Поэтому $$ M \geqslant4b-2N. \quad (2) $$
Из (1) и (2) следует, что $4b-2N\leqslant M\leqslant 2r-2N+2$. Поскольку $b+r=N^2$, получаем отсюда $6b\leqslant 2N^2+2$, или $$ b\leqslant N^2/3+1/3. $$ Поскольку $N^2=44^2\equiv 1 \pmod 3$, а $b$ целое, получаем нужный результат.
