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

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

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

Решение: Все числа имеют вид $2^x3^yz$, где $z$ взаимнопросто с 6. Для некоторого $z_i$, взаимнопростого с 6, рассмотрим множество точек целочисленной решётки с координатами $(x,y)$, таких что $2^x3^yz_i$ - одно из данных чисел(Назовём это множество $S_i$). Пусть количество точек $k_i$. Пара будет хорошей, если точки будут соседними - пусть $n_i$ количество таких пар.

Утверждение. $n_i\le 2(k_i-\sqrt{k_i})$

Доказательство. Рассмотрим строки(то есть точки с одинаковой ординатой) и столбцы. Пусть $S_i$ имеет $a$ непустых строк и $b$ непустых столбцов. Заметим, что если в строке $k$ точек, то количество соседних не более, чем $k-1$. Поэтому суммируя для каждой строки, получаем, что имеется не более $k_i-a$ пар по строкам. Аналогично имеется не более $k_i-b$ пар по столбцам. В итоге $s_i\le 2k_i-(a+b)\le2(k_i-\sqrt{ab})\le 2(k_i-\sqrt{k_i})$.$\square$

Теперь суммируя количество хороших пар для каждого $z$(очевидно, что при разных $z$ два числа не могут быть хорошими) получаем оценку для общего количества хороших пар $$n\le 2\sum(k_i-\sqrt{k_i})\le 2(100-\sqrt{\sum{k_i}})=180$$ Равенство достигается в случае, когда часть $z$ у всех чисел одинаковая и их множество $S$ на целочисленной плоскости образует квадрат $10\times10$.

Ответ: 180