ВсОШ 2023, 9 класс, задача 7
( баллов) На доску записали чисел, среди которых нет равных. В тетрадку выписали чисел — все разности двух чисел с доски (каждый раз из большего числа вычитали меньшее). Оказалось, что в тетрадке число записано ровно раз. Пусть — наибольшее число, записанное в тетрадке. Найдите наименьшее возможное значение .
(Л. Самойлов)
Ответ
Ответ. .
Решение. Докажем, что . Все числа с доски разбиваются на цепочки чисел вида так, что числа из разных цепочек не отличаются ровно на . Такое разбиение нетрудно построить, соединив любые два числа, отличающиеся на , отрезком и рассмотрев полученные ломаные.
Пусть получилось цепочек, в которых чисел соответственно (некоторые цепочки могут состоять из одного числа). В цепочке из чисел есть ровно пара чисел, отличающихся на . Поэтому общее количество единиц в тетрадке равно
откуда . Значит, в одной из цепочек не меньше, чем чисел, то есть не меньше чисел. Разность наибольшего и наименьшего чисел в такой цепочке не меньше .
Осталось привести пример, в котором . Такой пример дают, например, числа
Действительно, в этом примере , и ровно для первых из этих чисел в наборе есть число, на единицу большее.
Замечание. Приведённый пример — не единственный. Все возможные оптимальные примеры устроены так: есть ровно одна цепочка из чисел (от до ), а также цепочек, каждая — из чисел; все числа этих остальных цепочек должны располагаться между и .
Только ответ.
Приведён только пример с , удовлетворяющий условиям задачи.
Приведена только оценка, показывающая, что .
Сформулированное утверждение о том, что все числа разбиваются на цепочки, в каждой из которых числа отличаются на (а разности чисел из разных цепочек не равны ), принимается без доказательства. Сформулированное утверждение, что в цепочке из чисел не более единичных разностей, тоже принимается без доказательства.