Теория чисел на Высшей пробе
Ошибка.
Попробуйте повторить позже
На доске написано несколько цифр (среди них могут быть одинаковые). На каждом шаге две цифры стираются и пишутся цифры, из
которых состоит их произведение. (Например, вместо и
пишется
и
, а вместо
и
пишется
). Доказать, что через
несколько шагов на доске останется одна цифра.
Подсказка 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
Верно! Мы понимаем, что после каждого шага, на доске появляется цифра, которая меньше чем те, что были взяты. Ну предположим, что минимальная цифра не уменьшается бесконечно долго. Значит, она не участвует в операциях. Аналогично посмотрим на минимальную из оставшихся, она тоже бесконечно долго не уменьшается (иначе стала бы меньше глобального минимума). И так далее. Получаем что все цифры бесконечно долго не уменьшаются. Противоречие. (Это надо оформлять в общем виде) И так, что мы имеем?
При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр и
получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем
минимальная из цифр
.
Действительно, двузначные числа и
больше, чем
, так как
. Тем самым на каждом шаге либо
получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не
увеличивается.
_________________________________________________________________________________________________________________________________________________________________________________
Будем доказывать утверждение задачи индукцией по числу При
утверждение очевидно. Утверждение для
следует из
свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.
_________________________________________________________________________________________________________________________________________________________________________________
Пусть утверждение доказано для . Пусть
— минимальная из цифр, написанных на доске. Достаточно показать,
что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше
.
Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра , к которой очередной шаг задачи не
применяется: каждый шаг не затрагивает хотя бы одну цифру
. В противном случае, если осталась одна или две цифры
, и к ней
(соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу
свойства уменьшения первого разряда.
Вышесказанное эквивалентно тому, что все шаги задачи применяются к меньшему набору цифр: ко всем, кроме одной из цифр . А
тогда по предположению индукции через несколько шагов на доске, кроме цифры
, останется одна цифра. Это сводит шаг индукции к
случаю двух цифр, для которого утверждение задачи доказано.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!