Республиканская олимпиада по математике, 2019 год, 10 класс

Дана бесконечная клетчатая бумага с размером клеток $1$ см. В узлах клеток отмечено $2019$ точек так, что расстояние между любыми двумя отмеченными точками равно натуральному числу сантиметров. Докажите, что больше $333333$ из этих расстояний являются натуральными числами, которые делятся на $3$. ( С. Полянских )

Комментарий/решение

Решение можете посмотреть на данном сайте в разделе математика:

Республика 2019

Для каждой точки добавим целые координаты.

Будем использовать уравнение $(*)$ для двух точек $(x,y)$ и $(a,b)$:

$$(x-a)^2+(y-b)^2=r^2$$

где $r$- целое растояние.

Теперь 2019 точек разобьем на несколько множеств так что для любых двух точек $(x_1,y_1)$ и $(x_2,y_2)$ выполняются оба $3 \mid x_1-x_2$ и $3 \mid y_1-y_2$ тогда и только когда обе точки из одного множества.

Выберем произвольную точку $(x,y)$ из множества $A$. Определим количество множеств отличных от $A$ такие что выбрав точку $(a,b)$, ровно одно из $3\mid x-a$ и $3\mid y-b$ выполняется. Таких множеств не больше 4: не больше двух если выполняется первое, и не больше двух если второе. Теперь докажем что не существует $(a,b)$ что $(x-a)(y-b)$ не делится на 3. От противного, расмотрим такую точку. Используем $(*)$. Левая часть уравнения $(*)$ при делении на 3 дает остаток 2, а правая дает остаток 0 или 1. Противоречие.

Количество множеств не больше 5. Назначим $n_1, n_2, ..., n_5$ - количество точек в каждом множестве. Тогда количество расстоянии внутри множества с $n$ точками равно:

$$\frac{n^2-n}{2}$$

Убеждаемся что расстояния внутри одного множества делятся на 3 с $(*)$.

Общее количество расстоянии выполняющих условие задачи равно:

$$\frac{n_1^2+n_2^2+...+n_5^2-n_1-n_2-...-n_5}{2}$$

Используем $n_1+...+n_5=2019$ и:

$$n_1^2+...+n_5^2 \geq \frac{(n_1+...+n_5)^2}{5}=\frac{2019^2}{5}$$

$$\frac{n_1^2+n_2^2+...+n_5^2-n_1-n_2-...-n_5}{2} \geq \frac{2019^2-5\cdot 2019}{10}>400000$$