ВсОШ 2026, 11 класс, задача 6
На доску выписаны попарно различных натуральных чисел, больших . Оказалось, что для любого выписанного числа найдутся хотя бы пар выписанных чисел , для которых делится на . Найдите наибольшее возможное значение .
Ответ: .
Решение. Для начала приведём пример для . Пусть на доску выписаны числа .
Рассмотрим одно из выписанных чисел . Если , то в этом множестве найдётся число такое, что делится на , возможно, за исключением случаев и . Действительно, если — остаток от деления на , можно взять . Пусть . Тогда , что делится на . Таким образом, для каждого выписанного числа хотя бы выписанных числа участвуют хотя бы в одной искомой паре, поэтому таких пар не менее .
Далее докажем оценку. Пусть — наибольшее из чисел, выписанных на доске. Рассмотрим пары выписанных чисел , для которых делится на . Покажем, что число не участвует ни в одной из рассмотренных пар, а любое из оставшихся чисел — не более чем в одной такой паре, отсюда последует, что и .
Пусть делится на , где . Поскольку , то делится на , но , противоречие. Теперь пусть числа и делятся на , где — различные выписанные числа. Тогда число взаимно просто с и кратно . Значит, делится на , однако , полученное противоречие завершает решение задачи.