ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73662
Темы:    [ Десятичная система счисления ]
[ Примеры и контрпримеры. Конструкции ]
[ Индукция (прочее) ]
[ Принцип крайнего (прочее) ]
[ Доказательство от противного ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Для каждого натурального n обозначим через  s(n)  сумму цифр его десятичной записи. Назовём натуральное число m особым, если его нельзя представить в виде  m = n + s(n).  (Например, число 117 не особое, поскольку  117 = 108 + s(108),  а число 121, как нетрудно убедиться, – особое.) Верно ли, что особых чисел существует лишь конечное число?


Решение 1

  Рассмотрим все целые числа от 1 до какого-то N. Среди них найдётся некоторое количество  R(N)  особых чисел (например, число 1 – особое). Остается показать, что, выбирая соответствующим образом N, можно получить сколь угодно большое  R(N).

  Первый способ. Ясно, что  R(N)  не меньше, чем количество таких  n ≤ N,  для которых  n + s(n) > N.
  Возьмём  N = 1010k  и докажем, что  R(N) ≥ 10k.  Рассмотрим число M = N – 10k = 9...90...0  (10k девяток и k нулей). Если  M ≤ n < N,  то
n + s(n) ≥ N – 10k) + 9·10k > N.

  Второй способ. Ясно, что  R(N)  не меньше, чем количество таких пар чисел  m < n ≤ N,  для которых  m + s(m) = n + s(n).  Докажем, что
R(100k + 100) ≥ k.  Действительно, при каждом целом a от 1 до k для чисел  m = 1000a + 91 и n = 1000a + 100
m + s(m) = n + s(n) = 1000a + s(a) + 101.


Решение 2

  Докажем, что бесконечная последовательность, заданная соотношениями:  m0 = 9,  mk = mk–1 + 10k + 1,  состоит из особых чисел.
  Сначала докажем, что  11·10k–1 < mk < 2·10k  при  k > 1. Левое неравенство очевидно, а правое проверяется по индукции:
mk = mk–1 + 10k + 1 < 2·10k–1 + 10k + 1 = 12·10k–1 + 1 < 2·10k.
  Предположим, что в нашей последовательности есть неособое число; рассмотрим наименьший номер k, при котором  mk = n + s(n).  Заметим, что  k ≥ 3,  так так "особость" чисел  m1 = 9 + 11 = 20  и  m2 = 20 + 101 = 121  нетрудно проверить непосредственно.
  Докажем, что  10k < n < 2·10k.  Здесь правое неравенство очевидно, а левое доказывается от противного: если  n < 10k,  то
n + s(n) < 10k + 9k < 10k + 10k–1 = 11·10k–1 < mk  (9k < 10k–1  при k ≥ 3).
  Таким образом, десятичная запись числа n начинается с 1. Значит, число  l = n – 10k  получается из n отбрасыванием первой цифры. Следовательно,  s(l) = s(n) – 1,  и поэтому  l + s(l) = n – 10k + s(n) – 1 = mk – 10k – 1 = mk–1.  Противоречие, поскольку число mk–1 – особое.


Ответ

Неверно.

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

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 2
Задача
Номер М127

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .