Республиканская олимпиада по математике, 2001 год, 11 класс
Комментарий/решение:
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=(a−c)2+(b−d)2=m2, CD2=(c−x)2+d2=n2, BD2=(a−x)2+b2=z2
Решая систему и находя z2=t2+x2−± √(m+t−k)(k+m−t)(k−m+t)(k+m+t)(n+x−k)(k+n−x)(k−n+x)(k+n+x)+(k2−n2+x2)(k2−m2+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+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 то выражение √(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+k4≡ 2+1+1+1+1+1≡1 mod 3 и
2(kt)2+2(kx)2+(km)2+(kn)2+(mx)2+(tn)2≡ 2+2+1+1+1+1≡2 mod 3
То есть получаем 1≡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 всего их C4n=(n−3)(n−2)(n−1)n24, пусть X1Y1=s1 где слева возрастающие вершины к примеру 12, справа их количество во всех возможных четырёхугольниках,так же учитывается количество не повторение вершин в четырёхугольнике чтобы не считать их повторно, то есть для некоторого X2Y2=s2 где одна из вершин может совпадать с одной из предыдущей X1Y2=s2, учитываем что X1Y1,X2Y2 не образуют один и тот же четырёхугольник, аналогично для третьей пары, учитывается два предыдущих.
Значит надо минимизировать количество таких парных вершин и чтобы в сумме s1+...st=C4n.
Пусть количество точек (вершин) четна, тогда выбирая первую любую пару, сумма всегда будет постоянна s1=1+...+(n−3)=(n−2)(n−3)2, очевидно если s1>s2,...,st так как вершины расположены по возрастанию и всевозможно, значит чем больше s тем меньше отрезков понадобится.
Возьмём произвольную пару XY тогда A=s=(n−2)(n−3)2 если выбрать X1Y1 где одна из вершин будет совпадать то s1−s2>1 так как при упорядочивании на одну пустую вершину будет претендовать другие (по возрастанию), аналогично и для третьей, значит максимальный набор из s возможен, если разбить n точек по парам всего n2 и тогда когда вершины не будут иметь общих нумерации, то есть 12,34,56,...,(n−1)n тогда B=s1+s2+...+st=n2=A+A−1+A−2+A−3+...A−n2+1=n(n−2)(n−3)4−1+n2−12⋅(n2−1)=n(n−2)(2n−7)8
Тогда для произвольной паре (назовем ее «остаточной») всегда будем получать постоянную для него s сумму, так как при выше приведённой структуре расположении будут «затрагиваться» всегда две вершины из набора 12,34,.., откуда st+1=s1−((n−3)+(n−4)+n2−2)=(n−4)(n−6)2, тогда для последующих будет выполнятся st+1≥st+2 так как для них увеличивается число сходных вершин, тогда остаток для заполнении другими вершинами Z=C4n−B=n(n−2)(n−4)(n−6)24, значит минимальное количество вершин будет не меньше чем Z(n−4)(n−6)2+n2≥C2n6 решая неравенство получаем что это верно при n≥4.
Практический аналогично для n нечётных, только для «остаточного члена» выбираем 1n так как при данном выборе s для него максимизируется (значит минимизируется количество парных вершин) потому что последняя вершина n не входит не в одну парных вершин при наборе 12,34,..., все сводится к решению (n−1)(n+3)12≥n(n−1)2 которая верна для n≥4.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.