Loading [MathJax]/jax/output/SVG/fonts/TeX/fontdata.js

10-я Международная Жаутыковская олимпиада, 2014 год


Даны сто различных натуральных чисел. Назовем пару чисел хорошей, если числа в ней отличаются в 2 или в 3 раза. Какое наибольшее число хороших пар могут образовывать эти сто чисел? (Одно и то же число может входить в несколько пар.)
посмотреть в олимпиаде

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

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

Решение: Все числа имеют вид 2x3yz, где z взаимнопросто с 6. Для некоторого zi, взаимнопростого с 6, рассмотрим множество точек целочисленной решётки с координатами (x,y), таких что 2x3yzi - одно из данных чисел(Назовём это множество Si). Пусть количество точек ki. Пара будет хорошей, если точки будут соседними - пусть ni количество таких пар.

Утверждение. ni2(kiki)

Доказательство. Рассмотрим строки(то есть точки с одинаковой ординатой) и столбцы. Пусть Si имеет a непустых строк и b непустых столбцов. Заметим, что если в строке k точек, то количество соседних не более, чем k1. Поэтому суммируя для каждой строки, получаем, что имеется не более kia пар по строкам. Аналогично имеется не более kib пар по столбцам. В итоге si2ki(a+b)2(kiab)2(kiki).

Теперь суммируя количество хороших пар для каждого z(очевидно, что при разных z два числа не могут быть хорошими) получаем оценку для общего количества хороших парn2(kiki)2(100ki)=180Равенство достигается в случае, когда часть z у всех чисел одинаковая и их множество S на целочисленной плоскости образует квадрат 10×10.

Ответ: 180