Задание №176916: Турнир городов

3. В таблице 44 × 44 часть клеток синие, а остальные красные. Никакие синие клетки не
граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам
(от любой красной клетки можно добраться до любой другой красной, переходя из клетки в
клетку через общую сторону и не заходя в синие клетки). Докажите, что синих клеток в
таблице меньше трети.
Б.Френкин
Положим N = 44, и пусть b и r — количества синих и красных клеток. Оценим сверху
количество M общих сторон красных клеток с синими.
Всего у красных клеток 4r сторон, откуда M (cid:54) 4r. Вдоль краёв таблицы стоит не меньше 2N
сторон красных клеток, поэтому M (cid:54) 4r − 2N. Теперь рассмотрим граф, вершины которого —
красные клетки, а рёбра соединяют клетки, имеющие общую сторону. По условию граф связен,
поэтому количество его рёбер не меньше r − 1. Каждому из них отвечает общая сторона двух
красных клеток, засчитанная в величине 4r два раза, поэтому из M можно вычесть 2(r − 1).
Получаем
M (cid:54) 4r − 2N − 2(r − 1) = 2r − 2N + 2. (1)
Оценим теперь M снизу. Сложив количества сторон всех синих клеток, получим 4b. Ясно,
что на одной стороне таблицы не больше N/2 сторон синих клеток. Поэтому
M (cid:62) 4b − 2N. (2)

Из (1) и (2) следует, что 4b−2N (cid:54) M (cid:54) 2r −2N +2. Поскольку b+r = N2, получаем отсюда
6b (cid:54) 2N2 + 2, или
b (cid:54) N2/3 + 1/3.

Поскольку N2 = 442 ≡ 1 (mod 3), а b целое, получаем нужный результат.