Метод спуска, индукция и последовательное конструирование в ТЧ
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Дано натуральное число 
Для каждого натурального 
число 
получается так: 
умножают на 
, каждую цифру
десятичной записи произведения заменяют её остатком при делении на 
и получившуюся последовательность цифр рассматривают как
двоичную запись 
Докажите, что 
при всех достаточно больших 
Подсказка 1
Как доказывать периодичность? Вообще не очень понятно, поэтому предлагается доказать, что целая часть при делении a_i на 2^2021 стабилизируется. Более того целая часть будет нулем или единицей. Как после этого можно доказать, что остаток будет периодичен?
Подсказка 2
В задаче активно фигурирует двоичная запись числа, поэтому разумно остаток представить в двоичной записи. Так как остаток меньше 2^2021, то слагаемых будет не больше 2021. Как можно доказать, что они периодичны с периодом 2^2021?
Подсказка 3
Давайте доказывать наше предположение по индукции. Начните с последних разрядов, докажите, что слагаемое, помноженное на a_i, периодично с периодом равным 2^i. Примените предположение для всех меньших и решите задачу.
Обозначим операцию замены всех цифр числа 
в десятичной записи их остатками при делении на 
и рассмотрения последовательности
цифр, как двоичную запись, за 
Т.е. 
Пусть 
где 
и 
— целые числа. Докажем для начала, что начиная с некоторого 
число 
перестаёт меняться и равняется 
или 
Действительно, 
причём 
т.е. цифры (в
десятичной записи) чисел 
и 
не влияют друг на друга. Отсюда следует, что 
причём
заметим теперь, что 
для всех 
кроме 
и 
а 
и 
значит, начиная с некоторого
момента 
стабилизируется.
Докажем теперь, что последовательность 
периодична с периодом 
Пусть
т.е. посмотрим на двоичную запись числа 
Докажем, что 
периодична с периодом 
Доказывать будем индукцией по 
Для
утверждение следует из того, что 
нечётно, поэтому 
остаётся всегда одной чётности, поэтому 
не меняется. Теперь
докажем переход от всех чисел, меньших 
к 
 |
Заметим,
что выражение 
не влияет на последние 
цифру числа 
а значит не влияет
и на 
По предположению индукции числа
а с ним и переносы в 
-й разряд, периодичны с периодом 
а, значит, при увеличении 
на 
чётность 
не
изменится.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
