Разделы 
Дополнительно
Задача по математике - 3785
2019-06-16 
Дано простое число $p > 3$. Рассмотрим на координатной плоскости множество $M$, состоящее из таких точек с целыми координатами $(x, у)$, что $0 \leq x < p, 0 \leq y < p$. Докажите, что можно отметить $p$ различных точек множества $M$ так, чтобы никакие четыре из них не лежали в вершинах параллелограмма и никакие три из них не лежали на одной прямой.
Решение:
В качестве требуемого множества можно взять множество, состоящее из точек $A_k = (k; r(k)), k = 0, 1, 2, \cdots, p-1$, где $r(k)$ - остаток от деления $k^2$ на $p$. Для $p = 7$ это множество показано на рис.
Если бы какие-то три точки $A_l, A_m, A_n$ ($l < m < n < p$) лежали на одной прямой, то выполнялось бы соотношение
$\frac {r(m) - r(l)}{m - l} = \frac {r(n) - r(m)}{n - m}$,
т. е. для некоторых целых $a$ и $b$ выполнялось бы равенство $(n - m) (m^2 - l^2 + ap) = (m - l) (n^2 - m^2 + bp)$. Перенося члены, не содержащие $p$ в левую часть равенства, видим, что $(n - m) (m - l) (n - l)$ делится на $p$. Поскольку $p$ простое, это невозможно.
Если бы какие-то четыре точки $A_k, A_l, A_m, A_n$ лежали в вершинах параллелограмма, $\vec {A_kA_l} = \vec {A_n A_m}$, то выполнялись равенства $l - k = m - n$ и $r(l)- r(k) = r(m) - r(n)$, т. е. число $(l^2 - k^2) - (m^2 - n^2)$ делилось бы на $p$. Тогда число
$(l + k) - (m + n) = 2l - 2m$,
а поскольку $p > 3$, и $l - m$ также должно было бы делиться на $p$, что невозможно.
Дано простое число $p > 3$. Рассмотрим на координатной плоскости множество $M$, состоящее из таких точек с целыми координатами $(x, у)$, что $0 \leq x < p, 0 \leq y < p$. Докажите, что можно отметить $p$ различных точек множества $M$ так, чтобы никакие четыре из них не лежали в вершинах параллелограмма и никакие три из них не лежали на одной прямой.
Решение:
В качестве требуемого множества можно взять множество, состоящее из точек $A_k = (k; r(k)), k = 0, 1, 2, \cdots, p-1$, где $r(k)$ - остаток от деления $k^2$ на $p$. Для $p = 7$ это множество показано на рис.
Если бы какие-то три точки $A_l, A_m, A_n$ ($l < m < n < p$) лежали на одной прямой, то выполнялось бы соотношение
$\frac {r(m) - r(l)}{m - l} = \frac {r(n) - r(m)}{n - m}$,
т. е. для некоторых целых $a$ и $b$ выполнялось бы равенство $(n - m) (m^2 - l^2 + ap) = (m - l) (n^2 - m^2 + bp)$. Перенося члены, не содержащие $p$ в левую часть равенства, видим, что $(n - m) (m - l) (n - l)$ делится на $p$. Поскольку $p$ простое, это невозможно.
Если бы какие-то четыре точки $A_k, A_l, A_m, A_n$ лежали в вершинах параллелограмма, $\vec {A_kA_l} = \vec {A_n A_m}$, то выполнялись равенства $l - k = m - n$ и $r(l)- r(k) = r(m) - r(n)$, т. е. число $(l^2 - k^2) - (m^2 - n^2)$ делилось бы на $p$. Тогда число
$(l + k) - (m + n) = 2l - 2m$,
а поскольку $p > 3$, и $l - m$ также должно было бы делиться на $p$, что невозможно.
