Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела высшая проба
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#94877

На доске написано несколько цифр (среди них могут быть одинаковые). На каждом шаге две цифры стираются и пишутся цифры, из которых состоит их произведение. (Например, вместо 5  и 6  пишется 3  и 0  , а вместо 2  и 4  пишется 8  ). Доказать, что через несколько шагов на доске останется одна цифра.

Подсказки к задаче

Подсказка 1

Понятно, что мы хотим доказать, что что-то убывает, что-то уменьшается, а бесконечно это продолжаться не может, значит рано или поздно останется одна цифра. Намёк либо на какой-то полуинвариант, либо на индукцию по количеству чисел.

Подсказка 2

Возьмём две произвольные цифры a, b. Не умоляя общности, а ≥ b. b, a ≤ 9, значит, 10b > ab. То есть ab ≤ 10b - 1. Посмотрим внимательно на десятичные записи этих чисел. Какой вывод о них можно сделать?

Подсказка 3

Либо ab < 10 и оно однозначное, либо первая цифра ab < min(a,b) = b. Теперь надо выбрать, полуинвариант или индукция?

Подсказка 4

Допустим, полуинвариант. Нууу, у нас есть цифры на доске, причём перемножаться они могут хаотично. Как тогда следить за первыми цифрами получаемых произведений? Сумма цифр на доске, произведение — не подходят. Остальное тоже странно связано. Интересно, что же там насчёт индукции?

Подсказка 5

Начнём с базовых идей. Попробуем зацепиться за количество цифр на доске. Пусть изначальное количество цифр на доске — n. База для n = 1 тривиальна. Попробуем сделать переход.

Подсказка 6

Пусть мы доказали для n = k, докажем для n = k + 1. Заметим, что если в какой-то момент цифр на доске стало меньше, то в этом случае переход доказан, просто пользуемся предыдущими шагами индукции. Хорошо, а что если цифр не станет меньше? Как быть в этом случае? Напомню, первая цифра ab < min(a,b). На какую мысль нас это наталкивает?

Подсказка 7

Верно! Мы понимаем, что после каждого шага, на доске появляется цифра, которая меньше чем те, что были взяты. Ну предположим, что минимальная цифра не уменьшается бесконечно долго. Значит, она не участвует в операциях. Аналогично посмотрим на минимальную из оставшихся, она тоже бесконечно долго не уменьшается (иначе стала бы меньше глобального минимума). И так далее. Получаем что все цифры бесконечно долго не уменьшаются. Противоречие. (Это надо оформлять в общем виде) И так, что мы имеем?

Показать доказательство

При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр a  и    b  получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем минимальная из цифр a,b  .

Действительно, двузначные числа a0 =10× a  и b0 =10× b  больше, чем ab  , так как a,b< 9  . Тем самым на каждом шаге либо получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не увеличивается.

_________________________________________________________________________________________________________________________________________________________________________________

Будем доказывать утверждение задачи индукцией по числу n.  При n = 1  утверждение очевидно. Утверждение для n = 2  следует из свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для n =k  . Пусть m  — минимальная из цифр, написанных на доске. Достаточно показать, что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше m  .

Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра m  , к которой очередной шаг задачи не применяется: каждый шаг не затрагивает хотя бы одну цифру m  . В противном случае, если осталась одна или две цифры m  , и к ней (соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу свойства уменьшения первого разряда.

Вышесказанное эквивалентно тому, что все шаги задачи применяются к меньшему набору цифр: ко всем, кроме одной из цифр m  . А тогда по предположению индукции через несколько шагов на доске, кроме цифры m  , останется одна цифра. Это сводит шаг индукции к случаю двух цифр, для которого утверждение задачи доказано.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!