Тема . Курчатов
Теория чисел на Курчатове (с комбинаторными элементами)
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела курчатов
Решаем задачу:

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

Задача 1#70797

На доске написаны числа 2,3,5,...,2003,2011,2017,  т. е. все простые числа, не превосходящие 2020.  За одну операцию можно заменить два числа a,b  на максимальное простое число, не превосходящее √-2------2
 a − ab+ b.  После нескольких операций на доске осталось одно число. Какое максимальное значение оно может принимать?

Источники: Курчатов-2020, 11.3 (см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

Если бы ответ был бы огромным, его было бы очень сложно искать(и проверять большие числа на простоту). Поэтому попробуем найти ответ среди тех, что уже записывать. Допустим, мы сделали одну операцию. Что можно сказать про новое число. Как можно его ограничить?

Подсказка 2

Оно лежит между числами, которые заменили на него!(почему?). Тогда становится ясно, что 2017 не получить. А что получить можно и как?

Подсказка 3

Попробуем получить 2011! Работать с неизвестными нам простыми числами во второй тысяче сложно, поэтому попробуем найти алгоритм, которому не нужно точно описывать работу с ними. Как числа хотим оставить в конце для получения 2011?

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

Докажем неравенство a< √a2-− ab+-b2 <b  при условии a <b, a,b∈ℕ.  Для этого достаточно возвести его в квадрат и использовать             2      2        2            2
a <b  =⇒   a < ab <b   ⇐⇒   a − ab< 0, −ab+ b >0,  откуда сразу же получаем требуемое 2   2      2   2
a <a − ab+b < b .

Поскольку знаки везде строгие, то мы получаем простое следствие — число 2017  получиться не может, потому что каждое полученное простое будет меньше 2017.  Поэтому наибольшее число, которое мы теоретически можем получить, это 2011  (наибольшее простое меньше, чем 2017  ).

Теперь покажем, как строится пример: будем последовательно выбирать два наибольших простых числа из всех, игнорируя 2017.  Так всегда будет оставаться меньшее из этих чисел, поскольку большее остаться не может, при этом на каждом шаге мы рассматриваем два последовательных простых (это доказывается по индукции, поскольку на первом шаге мы оставим 2003  из пары 2003  и 2011,  и так далее). То есть на каждом шаге    √---------
a<  a2− ab +b2 < b,  при этом a,b  — последовательные простые, поэтому между ними других простых нет и мы будем выбирать a.

Наконец, останутся числа 2,2017,  для них покажем, что 2011  подходит

∘---------------
 20172− 2⋅2017+22 >2011 ⇐⇒   20172− 2⋅2017+ 22 > 20112 ⇐⇒   6⋅4028> 4030

Что и требовалось (в конце использована разность квадратов).

Замечание. Доказательство двойного неравенства    √ -2------2
a <  a − ab+ b < b  также можно произвести через теорему косинусов для угла   ∘
60 (в центре стоит длина третий стороны). При этом важно, что напротив угла в   ∘
60 всегда лежит средняя сторона треугольника. Также сразу можно определить критерий равенства.

Ответ:

 2011

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

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

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

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

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

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

Бесплатное обучение
в Школково

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

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

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

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

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

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

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

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!