Олимпиадная задача про Фому и Ерёму: последовательности и доказательство от противного
Задача
Неутомимые Фома и Ерёма строят последовательность. Сначала в последовательности одно натуральное число. Затем они по очереди выписывают следующие числа: Фома получает очередное число, прибавляя к предыдущему любую из его цифр, а Ерёма – вычитая из предыдущего любую из его цифр. Докажите, что какое-то число в этой последовательности повторится не меньше 100 раз.
Решение
Пусть первые два члена a1 и a2 последовательности меньше 10m. Докажем, что тогда и все остальные члены меньше 10m. Предположим противное и обозначим через n наименьший номер, при котором an ≥ 10m. Ясно, что этот член написан Фомой и an–1 ≥ 10m – 9. Тем более, an–2 ≥ 10m – 9, то есть все цифры числа an–2, кроме последней, – девятки. Но тогда Ерёма, вычитая из этого числа одну из его цифр, получит an–1 ≤ 10m – 10. Противоречие.
В силу бесконечности количества членов последовательности и конечности множества её значений по крайней мере один из её членов повторится бесконечное число раз.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь