Оценка + пример в задачах по теории чисел
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На доске написано 
различных натуральных чисел. Оказалось, что произведение любых ста из них делит произведение остальных.
Какое наибольшее количество простых чисел может быть написано на доске?
Подсказка 1
Про всю группу целиком тяжело говорить, но вот если рассмотреть делимость только на одно простое. Если мы берем некоторое простое p и говорим, что оно есть в нашем наборе, то какой набор из 100 чисел лучше всего рассмотреть(метод крайнего)?
Подсказка 2
Верно, стоит рассмотреть набор из 100 чисел, в который входят числа с наибольшей степенью вхождения этого p, так как тогда сумма степеней вхождения р в остальных числах должна быть больше или равна суммы степеней в этих 100. Что тогда можно сказать, про кол-во чисел, которые делятся на p из набора этих 100 чисел и из оставшегося набора?
Подсказка 3
Да, дело в том, что если у нас есть одно число кратное р(само р), то есть второе, так как если его нет, то мы могли бы взять это число в набор из 100 чисел и тогда условие бы про делимость не выполнялось бы. Аналогично, есть и третье число делящееся на р, четвертое и тд, до ста. При этом, когда у нас уже есть 100 чисел, которые кратны р, то если у нас нет еще 100 чисел кратных р, то условие про делимость будет нарушено. Значит, простых чисел не более 2021-199(так как 200 чисел, которые кратны р, но при этом простое только оно)=1822. Так, а может ли эта оценка достигаться?
Подсказка 4
Пупупу, если у нас есть 200 чисел кратных p, то мы можем расположить степени вхождения p в каждое из них в порядке возрастания и взять из них максимальные, тогда условие выполняться не будет… Но, если все степени – единицы, то всё хорошо и ничего не ломается! А не будет ли какое-то другое условие мешать нам построить пример с 1822 простыми?
Подсказка 5
Да, будет! Ведь, в таком случае на доске не может быть 2021 различное число! Ведь, в таком случае нам будет удовлетворять только один набор: 1822 простых числа, а все остальные – равны произведению этих простых, то есть равны между собой! Хм, следующее максимальное число простых — 1821. А может ли оно достигаться?
Подсказка 6
А вот 1821 простое может быть! Осталось только построить пример, где мы сможем показать, что существует такой набор, где найдется хотя бы 200 чисел, которые содержат каждое простое из нашего набора!
Пусть среди чисел есть какое-то простое 
, тогда чисел, которые ему кратны, хотя бы 
. Действительно, если взять те 
, в которые
входит в максимальной степени, то остальные должны давать степень 
, не меньшую суммарной среди взятых, откуда оставшихся
должно быть не меньше, чем взятых. Тогда простых среди чисел не более 
.
Если их ровно 
, то в силу условий выше мы можем сделать только набор
(иначе найдётся 
чисел, в которых суммарная степень 
больше, чем у оставшихся 
чисел)
Нетрудно видеть, что для этого набора НЕ выполнено условие о том, что на доске написано 
различных чисел.
Пример на 
простых чисел 
построим так: обозначим 
и рассмотрим
Теперь для любого простого 
заведомо найдётся хотя бы 
(их будет 
или 
) чисел, которые содержат 
. Поэтому в
произведение любых ста любой простой множитель входит не более, чем в степени 
, так что это произведение делит произведение
оставшихся чисел, в которое любой простой множитель входит в степени не меньше, чем 
.
_________________________________________________________________________________________________________________________________________________________________________________
Замечание.
Для 
простых пример 
(где 
) уже не сработает, ведь можно взять
набор
произведение чисел которого содержит множитель 
в сотой степени и не делит произведение оставшихся чисел.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
