Республиканская олимпиада по математике, 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$$

Пусть точками будут $A_1;A_2;...;A_{2019}$

Введем координатную плоскость да так, что какая та точка будет $A_1=(0;0)$

А для остальных $A_i=(x_i;y_i)$

(по сути это не нужно, просто так меньше печатать)

Тогда расстояние между точками $A_1A_i^2=x_i^2+y_i^2$

Рассмотрим это через $\pmod{3}$, и поймем, что либо всегда $3 \mid x_i$ либо всегда $3 \mid y_i$

Б.О.О. пусть это будет $x_i$.

(Если кажется, что найдется $A_n$ для которого $3 \nmid x_n; 3 \mid y_n$, то просто рассмотрите любую длину $A_nA_i \ (i \neq n)$)

Т.е. у нас все точки вида

$(3k;3m); (3k;3m+1); (3k;3m+2)$

Пусть их количество $a;b;c$ соответственно. $a+b+c=2019$

Тогда кол-во длин, которые делятся на $3$ будут

$C^2_a+C^2_b+C^2_c$

Очевидно, что если нужно минимизировать эту сумму, то нужно пытаться раскидать $a;b;c$ по ровну между собой (это легко понять т.к. если существует кучка по меньше чем на 2 чем остальные, и закинуть туда одну точку из более большой кучки, то количество пар уменьшится)

Тогда $C^2_a+C^2_b+C^2_c \geq 3C^2_{673}>333333$ ЧТД