Задача 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 = 10^10k  и докажем, что  R(N) ≥ 10^k.  Рассмотрим число M = N – 10^k = 9...90...0  (10^k девяток и k нулей). Если  M ≤ n < N,  то
n + s(n) ≥ N – 10^k) + 9·10^k > 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

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

Ответ

Неверно.

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

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