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

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

Условие

  Обозначим через S(k) сумму цифр натурального числа k. Натуральное число a назовём n-хорошим, если существует такая последовательность натуральных чисел a0, a1, ..., an, что  an = a  и  ai+1 = ai – S(ai)  при всех  i = 0, 1, ..., n – 1.  Верно ли, что для любого натурального n существует натуральное число, являющееся n-хорошим, но не являющееся (n+1)-хорошим?


Решение

  Для натуральных n и k введём обозначения  f(n) = n – S(n)  и  f k(n) = f(f(...(n)...))  (k раз). При увеличении числа n на 1, число S(n) либо увеличивается на 1 (если n не заканчивается на 9), либо уменьшается. Это значит, что функция f не убывает, причём  f(n + 10) > f(n)  при всех n.

  Первый способ. Выберем такое натуральное d, что  10d > 20d(n + 1),  и положим   k = 10d.  Пусть  b0 = 10k – 1,  c0 = 10k – kbi = f i(b0),  ci = f i(c0).  Докажем, что  bn > cn > bn+1.     (*)
  Так как  S(c0) ≤ 9k,  по индукции получаем  ci ≥ 10k – k – 9ki.  При  i ≤ n + 1  имеем  (9i + 1)k ≤ 10ki ≤ 10d+1(n+1) < 102d,  а значит, в числе ci хотя бы
k – 2d  первых цифр – девятки. Поэтому  S(ci) ≥ 9(k – 2d),  откуда (опять по индукции)  ci ≤ 10k – k – 9(k – 2d)i.  Итак,
10k – (9i + 1)k ≤ ci ≤ 10k – k – 9(k – 2d)i.
  Аналогично получаются оценки  10k – 9ki – 1 ≤ bi ≤ 10k – 1 – 9(k – 2d)i.
  Таким образом, для доказательства неравенства  cn < bn  достаточно проверить, что  10k – k – 9(k – 2d)n < 10k – 9kn – 1,  то есть  k > 18dn + 1.  Это верно в силу выбора d. Чтобы доказать неравенство  bn+1 < cn,  достаточно проверить, что
10k – 1 – 9(k – 2d)(n + 1) < 10k – (9n + 1)k,  то есть  8k + 1 > 18d(n + 1),  что тоже верно.
  Поскольку  cn = f n(c0),  то число cn является n-хорошим. В то же время, если  xb0,  то  f n+1(x) ≤ f n+1(b0) = bn+1 < cn.  Если же  x > b0,  то
f (x) ≥ f(10k) = b0,  и поэтому  f n+1(x) ≥ f n(b0) = bn > cn.  Следовательно, cn не является (n+1)-хорошим.

  Второй способ. Предположим противное: любое n-хорошее число x является (n+1)-хорошим. Это значит, что  x = f n+1(y)  при некотором y. Тогда число  f(y) является n-хорошим – а значит, и (n+1)-хорошим; из этого, в свою очередь следует, что x является (n+2)-хорошим. Аналогично показывается, что любое n-хорошее число является (n+k)-хорошим при всех натуральных k; назовём такое число просто хорошим.
  Выберем натуральное k > 3·10n и оценим количество Dk хороших k-значных чисел двумя способами.
  1. Для каждого числа  y ∈ [2·10k–1, 10k)  число  g(y) = f n(y)  является хорошим. Кроме того,  g(y) ≥ y – 9kn ≥ y – 10k–1 ≥ 10k–1,  то есть g(y) – хорошее k-значное число. С другой стороны, уравнение  f(x) = a  имеет не более 10 решений при любом a, поэтому уравнение  g(y) = a  имеет не более 10n решений. Значит,  
  2. Пусть x – хорошее k-значное число. Тогда  x = f 10k(y)  при некотором y. Так как  f 10k(y) ≤ y – 10k,  число y хотя бы (k+1)-значно. Пусть s – наименьшее число, для которого  f s(y)  является k-значным числом. Тогда  f s–1(y) ≥ 10k,  откуда  f s(y) = f(f s–1(y)) ≥ f(10k) = 10k – 1.  Таким образом,
f s(y) = 10k – 1,  то есть любое k-значное хорошее число есть  f t(10k – 1)  при некотором t.
  Покажем, что число  f t(10k – 1)  может являться k-значным лишь при     отсюда будет следовать, что     что противоречит оценке из предыдущего пункта. Положим  b0 = 10k – 1,  bi = f i(b0).  Достаточно доказать, что  bt0 < 10k–1.
  Предположим противное; тогда все числа bi при  i ≤ t0  являются k-значными. Оценим количество таких индексов  i < t 0,  что  bi – bi+1 < k  (то есть  S(bi) < k).  Цифры любого такого числа bi образуют последовательность из k неотрицательных целых чисел с суммой, не большей  k – 1.  Но существует ровно    таких последовательностей (это легко выводится из задачи 30719 б). Значит, и требуемых индексов не больше чем  .
  Итак, в последовательности b0, b1, ..., bt0  следующее число меньше предыдущего хотя бы на k как минимум в  t0 – 22k–1  случаях. Заметим, что     поскольку  k·22k–1 ≤ 10k.  Поэтому  bt0b0 – (t0 – 22k–1)k ≤ 10k – 10k = 0.  Противоречие.


Ответ

Верно.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2014/2015
этап
Вариант 5
класс
Класс 10
задача
Номер 10.4

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

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