Тема . Высшая проба

Теория чисел на Высшей пробе

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела высшая проба

Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#67768

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

Источники: Высшая проба - 2023, 11.3 (см. olymp.hse.ru)

Показать ответ и решение

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

Складывая эти три неравенства, получаем

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

Нужна консультация? Задайте нам вопрос в чате.

people

Специальные программы

Все специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse

cyberpunkMouse