Задача 98458

Темы:    [ Последовательности (прочее) ] [ Процессы и операции ] [ Десятичная система счисления ] [ Доказательство от противного ]

Сложность: 4 Классы: 8,9

Условие

Авторы: Генкин С.А., Шаповалов А.В.

Неутомимые Фома и Ерёма строят последовательность. Сначала в последовательности одно натуральное число. Затем они по очереди выписывают следующие числа: Фома получает очередное число, прибавляя к предыдущему любую из его цифр, а Ерёма – вычитая из предыдущего любую из его цифр. Докажите, что какое-то число в этой последовательности повторится не меньше 100 раз.

Решение

  Пусть первые два члена a₁ и a₂ последовательности меньше 10^m. Докажем, что тогда и все остальные члены меньше 10^m. Предположим противное и обозначим через n наименьший номер, при котором  a_n ≥ 10^m.  Ясно, что этот член написан Фомой и  a_n–1 ≥ 10^m – 9.  Тем более,  a_n–2 ≥ 10^m – 9,  то есть все цифры числа a_n–2, кроме последней, – девятки. Но тогда Ерёма, вычитая из этого числа одну из его цифр, получит  a_n–1 ≤ 10^m – 10.  Противоречие.
  В силу бесконечности количества членов последовательности и конечности множества её значений по крайней мере один из её членов повторится бесконечное число раз.

Замечания

1. Баллы: 8-9 кл. – 8, 10-11 кл. – 6.

2. В Задачнике "Кванта" число 100 в условии было заменено на 10.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1999/2000
Номер	21
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	5
журнал
Название	"Квант"
год
Год	2000
выпуск
Номер	1
Задача
Номер	М1727
олимпиада
Название	Турнир городов
Турнир
Дата	1999/2000
Номер	21
вариант
Вариант	осенний тур, основной вариант, 10-11 класс
Задача
Номер	3