10-я Международная Жаутыковская олимпиада, 2014 год
Комментарий/решение:
Решение: Все числа имеют вид 2x3yz, где z взаимнопросто с 6. Для некоторого zi, взаимнопростого с 6, рассмотрим множество точек целочисленной решётки с координатами (x,y), таких что 2x3yzi - одно из данных чисел(Назовём это множество Si). Пусть количество точек ki. Пара будет хорошей, если точки будут соседними - пусть ni количество таких пар.
Утверждение. ni≤2(ki−√ki)
Доказательство. Рассмотрим строки(то есть точки с одинаковой ординатой) и столбцы. Пусть Si имеет a непустых строк и b непустых столбцов. Заметим, что если в строке k точек, то количество соседних не более, чем k−1. Поэтому суммируя для каждой строки, получаем, что имеется не более ki−a пар по строкам. Аналогично имеется не более ki−b пар по столбцам. В итоге si≤2ki−(a+b)≤2(ki−√ab)≤2(ki−√ki).◻
Теперь суммируя количество хороших пар для каждого z(очевидно, что при разных z два числа не могут быть хорошими) получаем оценку для общего количества хороших парn≤2∑(ki−√ki)≤2(100−√∑ki)=180Равенство достигается в случае, когда часть z у всех чисел одинаковая и их множество S на целочисленной плоскости образует квадрат 10×10.
Ответ: 180
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.