Теория чисел на устном туре Турнира Городов
Ошибка.
Попробуйте повторить позже
Пусть 
— набор из 
различных натуральных чисел. Для каждой пары чисел 
где 
подсчитаем, сколько
чисел в 
являются делителями числа 
Какое наибольшее значение может принимать сумма полученных 
чисел?
Источники:
Подсказка 1
Что нужно делать в первую очередь, когда проверяем делимость у каких-то элементов последовательности без привязи к их позиции?
Подсказка 2
Упорядочим числа набора! Подумайте, на каких позициях относительно двух элементов могут находиться делители их разности?
Подсказка 3
Для конкретного k и j найдите количество и aᵢ, таких что aⱼ - aᵢ делится на aₖ.
Сначала докажем оценку. Пусть 
— элементы набора 
Заметим, что разность вида 
при 
может делиться на 
лишь при 
Выберем любые 
и посмотрим, сколько из чисел вида 
(при 
) может делиться на 
Все такие числа при 
отличаются менее, чем на 
поэтому на 
может
делиться лишь одно из них. Значит, всего таких разностей может быть максимум 
Итого, получаем
оценку:
Это количество достигается, например, на наборе 
Здесь все неравенства из оценки обращаются в равенства, а значит, и
оценка достигается.
Есть и другие примеры, в том числе, в которых все числа набора попарно взаимно простые, скажем,
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
