Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления
Ошибка.
Попробуйте повторить позже
Какое наибольшее количество натуральных чисел от 
до 
можно покрасить в желтый цвет так, чтобы произведение любых двух
желтых чисел не было желтым?
Подсказка 1
Давайте сначала построим пример, а потом попробуем сделать оценку) Какими хочется видеть жёлтые числа, чтобы с легкостью сказать, является ли их произведение жёлтым?
Подсказка 2
Обратите внимание на то, что числа у нас ограничены по величине.
Подсказка 3
Если сделать жёлтые числа достаточно большими, то и произведение будет слишком большим! Отсюда мы можем построить предполагаемый пример ;)
Подсказка 4
После построения предполагаемого примера мы видим, что "запрещено" чисел не так уж и много! Работать сразу на большом множестве чисел неудобно, давайте попробуем разбить на группы, где нам будет удобно "запретить" красить некоторое количество чисел.
Подсказка 5
Нам нужны такие тройки, где мы сможем запретить по числу ;)
Заметим, что единица не окрашена, так как 
Кроме того, в паре 
одно из чисел не окрашено. Рассмотрим набор чисел
Все эти числа различны, так как 
Разобьём их на тройки
вида 
где ![n ∈[1;48].](/api/latex-service/v1/GetSession/133066/index-76e39025653640b0fc8e781a53c968c6.svg)
Поскольку 
в каждой тройке есть хотя бы одно неокрашенное
число, а всего имеется 
таких троек. Таким образом, мы нашли 
неокрашенных чисел, поэтому количество жёлтых чисел не
превосходит 
Покажем, что эта оценка реализуется. Покрасим все числа от 
до 
Такая раскраска нам подходит, поскольку произведение
любых двух жёлтых чисел больше 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
