Математикадан республикалық олимпиада, 2000-2001 оқу жылы, 11 сынып

Жазықтықта $n$ нүкте орналасқан ($n\ge 4$). Кез келген екі нүктесінің арақашықтығы бүтін сан болып табылады. Әрқайсысы 3-ке бөлінетін, кем дегенде $1/6$ арақашықтық табылатынын дәлелдеңдер.

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

1) Докажем что если существует четыре точки, расстояния между любыми двумя из них целое число, то найдется как минимум $1$ отрезок, кратный $3$.

Пусть на плоскости имеются точки, с координатами $A(0,0) , D(x,0) , B(a,b) ,C(c,d)$ где $x$ целое.

Тогда $AC^2=c^2+d^2=k^2, \ AB^2=a^2+b^2=t^2, \ BC^2=(a-c)^2+(b-d)^2=m^2, \ CD^2=(c-x)^2+d^2=n^2, \ BD^2=(a-x)^2+b^2=z^2$

Решая систему и находя $z^2=t^2+x^2-\dfrac{\pm \ \sqrt{(m+t-k)(k+m-t)(k-m+t)(k+m+t)(n+x-k)(k+n-x)(k-n+x)(k+n+x)}+(k^2-n^2+x^2)(k^2-m^2+t^2)}{2k^2}$

Преобразовывая

$2(kz)^2+(tx)^2+(mn)^2+(kt)^2+(kx)^2+k^4=2(kt)^2+2(kx)^2+(km)^2+(kn)^2+(mx)^2+(tn)^2 \pm \sqrt{(m+t-k)(k+m-t)(k-m+t)(k+m+t)(n+x-k)(k+n-x)(k-n+x)(k+n+x)}$

Если $k,t,m,n,z,x$ числа не кратны $3$ то выражение $\sqrt{(m+t-k)(k+m-t)(k-m+t)(k+m+t)(n+x-k)(k+n-x)(k-n+x)(k+n+x)}=3v$ кратно $3$ но

$2(kz)^2+(tx)^2+(mn)^2+(kt)^2+(kx)^2+k^4 \equiv \ 2+1+1+1+1+1 \equiv 1 \ mod \ 3$ и

$2(kt)^2+2(kx)^2+(km)^2+(kn)^2+(mx)^2+(tn)^2 \equiv \ 2+2+1+1+1+1 \equiv 2 \ mod \ 3$

То есть получаем $1 \equiv 2+3v \ mod \ 3$ что неверно , значит хотя бы одно из $k,t,m,n,z,x$ кратно $3$.

2)

Прономеруем вершины как $1,2,3,4,5,...,n$ и разобьём его на четырёхугольники $1234,1235,1236,...,(n-3)(n-2)(n-1)n$ всего их $C_{n}^4=\dfrac{(n-3)(n-2)(n-1)n}{24}$, пусть $X_{1}Y_{1}=s_{1}$ где слева возрастающие вершины к примеру $12$, справа их количество во всех возможных четырёхугольниках,так же учитывается количество не повторение вершин в четырёхугольнике чтобы не считать их повторно, то есть для некоторого $X_{2}Y_{2}=s_{2}$ где одна из вершин может совпадать с одной из предыдущей $X_{1}Y_{2}=s_{2}$, учитываем что $X_{1}Y_{1},X_{2}Y_{2}$ не образуют один и тот же четырёхугольник, аналогично для третьей пары, учитывается два предыдущих.

Значит надо минимизировать количество таких парных вершин и чтобы в сумме $s_{1}+...s_{t}=C_{n}^4$.

Пусть количество точек (вершин) четна, тогда выбирая первую любую пару, сумма всегда будет постоянна $s_{1}=1+...+(n-3)=\dfrac{(n-2)(n-3)}{2}$, очевидно если $s_{1}>s_{2},...,s_{t}$ так как вершины расположены по возрастанию и всевозможно, значит чем больше $s$ тем меньше отрезков понадобится.

Возьмём произвольную пару $XY$ тогда $A=s=\dfrac{(n-2)(n-3)}{2}$ если выбрать $X_{1}Y_{1}$ где одна из вершин будет совпадать то $s_{1}-s_{2}>1$ так как при упорядочивании на одну пустую вершину будет претендовать другие (по возрастанию), аналогично и для третьей, значит максимальный набор из $s$ возможен, если разбить $n$ точек по парам всего $\dfrac{n}{2}$ и тогда когда вершины не будут иметь общих нумерации, то есть $12,34,56,...,(n-1)n$ тогда $B=s_{1}+s_{2}+...+s_{t=\dfrac{n}{2}}=A+A-1+A-2+A-3+...A-\dfrac{n}{2}+1 = \dfrac{n(n-2)(n-3)}{4}-\dfrac{1+\dfrac{n}{2}-1}{2} \cdot (\dfrac{n}{2}-1) = \dfrac{n(n-2)(2n-7)}{8}$

Тогда для произвольной паре (назовем ее «остаточной») всегда будем получать постоянную для него $s$ сумму, так как при выше приведённой структуре расположении будут «затрагиваться» всегда две вершины из набора $12,34,..,$ откуда $s_{t+1}=s_{1}-((n-3)+(n-4)+\dfrac{n}{2}-2) = \dfrac{(n-4)(n-6)}{2}$, тогда для последующих будет выполнятся $s_{t+1} \geq s_{t+2}$ так как для них увеличивается число сходных вершин, тогда остаток для заполнении другими вершинами $Z=C_{n}^4-B=\dfrac{n(n-2)(n-4)(n-6)}{24}$, значит минимальное количество вершин будет не меньше чем $\dfrac{Z}{\dfrac{(n-4)(n-6)}{2}}+\dfrac{n}{2} \geq \dfrac{C_{n}^2}{6}$ решая неравенство получаем что это верно при $n \geq 4$.

Практический аналогично для $n$ нечётных, только для «остаточного члена» выбираем $1n$ так как при данном выборе $s$ для него максимизируется (значит минимизируется количество парных вершин) потому что последняя вершина $n$ не входит не в одну парных вершин при наборе $12,34,...$, все сводится к решению $\dfrac{(n-1)(n+3)}{12} \geq \dfrac{n(n-1)}{2}$ которая верна для $n \geq 4$.

Число отрезков кратных 3 не равно числу четырёхугольников. Потому что один отрезок может быть стороной для нескольких четырёхугольника.

Благодарю.