ПитерГор 2024
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На числовой оси отмечено 2 000 000 точек с целыми координатами. Рассматриваются отрезки длин 97, 100 и 103 с концами в этих точках. Какое наибольшее количество таких отрезков может быть?
Источники:
Подсказка 1
Возьмем, например, отрезки длины 97. Рассмотрите цепочки из них и ответьте на следующий вопрос: чему будет равно количество отрезков в такой цепочке?
Подсказка 2
Да, отрезков в цепочке будет на 1 меньше, чем точек в цепочке. Тогда суммарное количество отрезков длины 97 будет (N - a), где a — количество цепочек.
Подсказка 3
Проделайте аналогичные рассуждения для отрезков длины 100 и 103. Предъявите в виде равенства общее число отрезков и критерий состоятельности оценки.
Подсказка 4
Критерий: a + b + c ≥ 97 + 100 + 103, где b и c — количества цепочек для чисел 100 и 103 соответственно.
Подсказка 5
Для проверки критерия предположите, что по какому-то из модулей присутствуют не все остатки.
Подсказка 6
Дело за малым: вычислите точное количество отрезков и предъявите ответ.
Пример: Указанное количество отрезков получается, если отметить на числовой оси 
последовательных целых
чисел.
Оценка: Покрасим отрезки длины 
и 
в красный, синий и зелёный цвета соответственно. Все 
точек
разобьются на 
красных цепочек. В каждой такой цепочке остатки всех чисел по модулю 
одинаковы, а количество отрезков ровно на
меньше, чем точек. Поэтому суммарное количество красных отрезков равно 
Аналогично, пусть имеется 
синих и 
зелёных цепочек. Тогда общее количество отрезков равно:
Оценка будет доказана, если мы проверим, что
Если у исходных 
чисел присутствуют все возможные остатки по каждому из модулей 
и 
то 
и
нужное неравенство очевидно.
Предположим теперь, что по одному из трёх модулей (например, по модулю 
) присутствуют не все остатки. Тогда в каждой синей
цепочке (которая соответствует отрезкам длины 
) содержится не более чем 
точек. Действительно, переход от числа 
к числу
по синему отрезку соответствует прибавлению 
по модулю 
Если бы присутствовали все 
остатков, то в цепочках было бы
не менее 
точек. Следовательно,
Аналогично, для зелёных цепочек (длина 
модуль 
):
Таким образом,
что при 
уже гораздо больше, чем 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
