Loading [MathJax]/jax/output/SVG/jax.js

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


На плоскости имеется n4 точек, расстояние между любыми двумя из которых есть целое число. Докажите, что найдется не менее 16 расстояний, каждое из которых делится на 3.
посмотреть в олимпиаде

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

пред. Правка 2   3
5 года 1 месяца назад #

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

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

Тогда AC2=c2+d2=k2, AB2=a2+b2=t2, BC2=(ac)2+(bd)2=m2, CD2=(cx)2+d2=n2, BD2=(ax)2+b2=z2

Решая систему и находя z2=t2+x2± (m+tk)(k+mt)(km+t)(k+m+t)(n+xk)(k+nx)(kn+x)(k+n+x)+(k2n2+x2)(k2m2+t2)2k2

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

2(kz)2+(tx)2+(mn)2+(kt)2+(kx)2+k4=2(kt)2+2(kx)2+(km)2+(kn)2+(mx)2+(tn)2±(m+tk)(k+mt)(km+t)(k+m+t)(n+xk)(k+nx)(kn+x)(k+n+x)

Если k,t,m,n,z,x числа не кратны 3 то выражение (m+tk)(k+mt)(km+t)(k+m+t)(n+xk)(k+nx)(kn+x)(k+n+x)=3v кратно 3 но

2(kz)2+(tx)2+(mn)2+(kt)2+(kx)2+k4 2+1+1+1+1+11 mod 3 и

2(kt)2+2(kx)2+(km)2+(kn)2+(mx)2+(tn)2 2+2+1+1+1+12 mod 3

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

2)

Прономеруем вершины как 1,2,3,4,5,...,n и разобьём его на четырёхугольники 1234,1235,1236,...,(n3)(n2)(n1)n всего их C4n=(n3)(n2)(n1)n24, пусть X1Y1=s1 где слева возрастающие вершины к примеру 12, справа их количество во всех возможных четырёхугольниках,так же учитывается количество не повторение вершин в четырёхугольнике чтобы не считать их повторно, то есть для некоторого X2Y2=s2 где одна из вершин может совпадать с одной из предыдущей X1Y2=s2, учитываем что X1Y1,X2Y2 не образуют один и тот же четырёхугольник, аналогично для третьей пары, учитывается два предыдущих.

Значит надо минимизировать количество таких парных вершин и чтобы в сумме s1+...st=C4n.

Пусть количество точек (вершин) четна, тогда выбирая первую любую пару, сумма всегда будет постоянна s1=1+...+(n3)=(n2)(n3)2, очевидно если s1>s2,...,st так как вершины расположены по возрастанию и всевозможно, значит чем больше s тем меньше отрезков понадобится.

Возьмём произвольную пару XY тогда A=s=(n2)(n3)2 если выбрать X1Y1 где одна из вершин будет совпадать то s1s2>1 так как при упорядочивании на одну пустую вершину будет претендовать другие (по возрастанию), аналогично и для третьей, значит максимальный набор из s возможен, если разбить n точек по парам всего n2 и тогда когда вершины не будут иметь общих нумерации, то есть 12,34,56,...,(n1)n тогда B=s1+s2+...+st=n2=A+A1+A2+A3+...An2+1=n(n2)(n3)41+n212(n21)=n(n2)(2n7)8

Тогда для произвольной паре (назовем ее «остаточной») всегда будем получать постоянную для него s сумму, так как при выше приведённой структуре расположении будут «затрагиваться» всегда две вершины из набора 12,34,.., откуда st+1=s1((n3)+(n4)+n22)=(n4)(n6)2, тогда для последующих будет выполнятся st+1st+2 так как для них увеличивается число сходных вершин, тогда остаток для заполнении другими вершинами Z=C4nB=n(n2)(n4)(n6)24, значит минимальное количество вершин будет не меньше чем Z(n4)(n6)2+n2C2n6 решая неравенство получаем что это верно при n4.

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

  2
5 года 2 месяца назад #

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

  1
5 года 1 месяца назад #

Благодарю.