|
|
 |
Условие
Обозначим через 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 – k, bi = 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-хорошим. В то же время, если x ≤ b0, то
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. Поэтому bt0 ≤ b0 – (t0 – 22k–1)k ≤ 10k – 10k = 0. Противоречие.
Ответ
Верно.
