Всесиб 2024, отборочный этап, 9 класс, задача 5
( баллов) Обозначим за множество из точек координатной плоскости с координатами , где и пробегают все натуральные числа от до включительно. Найдите наименьшее натуральное число такое, что среди любых точек множества всегда найдутся четыре, являющихся вершинами параллелограмма. Стороны параллелограмма могут быть наклонными — не горизонтальными и не вертикальными.
Ответ
Ответ. .
Решение. Пример точек, никакие четыре из которых не являются вершинами параллелограмма, дают все отмеченные точки, одна или обе координаты которых равна .
Если , то достаточно взять любые из этих точек. Следовательно, искомое в условии число не меньше, чем .
Докажем, что, если , то среди любых точек из всегда найдутся четыре, являющихся вершинами параллелограмма, две противоположных стороны которого вертикальны. Назовём эти точек отмеченными, рассмотрим все вертикали множества , содержащие ненулевое количество отмеченных точек. Занумеруем их числами , и обозначим количество отмеченных в них точек за соответственно. На -ой вертикали можно указать отрезков различной длины с концами в точках из — это все отрезки с нижним концом, совпадающим с самой нижней отмеченной точкой на этой вертикали. Всего на всех вертикалях можно таким образом указать
отрезков, каждый из которых имеет одну из возможных длин . Если , то и некоторые из указанных вертикальных отрезков имеют одинаковую длину. По построению, эти отрезки не могут лежать на одной вертикали, следовательно, их концы являются вершинами невырожденного параллелограмма с вершинами в отмеченных точках.