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