ПВГ 2024, 9 класс, задача 4
На плоскости покрашены в черный цвет точки с целыми координатами , где принимают целые значения от до (т.е. всего точек). Найдите максимальное число точек, которые можно перекрасить в красный цвет с соблюдением условия: каждый отрезок, концы которого окрашены в красный цвет содержит по крайней мере одну точку, покрашенную в черный.
Ответ
Ответ: .
Решение: Разобьем точки на квадраты (см. рис.) их будет , очевидно, что по условию нельзя ставить две красные точки в один квадрат. Значит можно покрасить не более
Покажем, как покрасить . – покрасим точки с координатами вида , где – целые. Докажем, что каждый отрезок с красными концами содержит черную точку. Доказываем индукцией по квадрату длины отрезка, которая может принимать только целые значения.
База – квадрат длины равен (меньше не может быть). Для него утверждение очевидно: отрезок содержит черную точку , аналогично и .
Шаг индукции. Соединим отрезком точки и . Рассмотрим середину отрезка . Если она черная, то все доказано. Если же она красная, то отрезок в два раза короче и на нем, по предположению индукции, есть черная точка.