ВСОШ 2026, региональный этап, 9 класс, задача 2

Ответ. .

Решение.

Оценка. Рассмотрим в нашем квадрате любые две клетки, имеющие общую сторону. У них всего вершин; расстояние между любыми двумя из них не превосходит . Но какие-то из этих двух точек имеют один и тот же цвет, так что в любом случае найдутся две одноцветных точки на расстоянии, не большем .

Пример. На самом деле, можно раскрасить не только данные точки, но и все вершины клеток бесконечной клетчатой плоскости так, чтобы расстояния между одноцветными точками было не меньше . Пример такой раскраски приведён на рисунке ниже (она переходит в себя при сдвиге на вдоль любой из координатных осей). В этой раскраске одним цветом окрашены все точки с целыми координатами , для которых число даёт фиксированный остаток при делении на .

Замечание. Как ни странно, существуют и другие способы доказать оценку. Например, можно заметить, что точек одного из цветов не меньше ; однако все точки нетрудно разбить даже на группы, в каждой из которых точки удалены друг от друга не более чем на (например, это можно сделать так, чтобы в каждой группе точки были вершинами двух клеток, имеющих общее ребро). Значит, в одной из групп окажутся две точки нашего цвета, и расстояние между ними будет не больше .