Задача 67412
|
|
 |
Условие
Для какого наибольшего $N$ существует $N$-значное число со свойством: в его десятичной записи среди любых нескольких подряд идущих цифр какая-то цифра встречается ровно один раз?Решение
Будем называть числа со свойством из условия хорошими, включая также «числа», начинающиеся на $0$. Докажем по индукции, что в хорошем числе, содержащем $k$ различных цифр $(1 \leqslant k \leqslant 10)$, не более $2^k – 1$ знаков.База ($k = 1$) очевидна – используется лишь одна цифра, и она не может повторяться.
Шаг индукции. Пусть $1 \leqslant k \leqslant 9$ и $X$ – хорошее число, содержащее $k+1$ различных цифр. По условию одна из цифр $a$ встречается в нём ровно один раз. Заметим, что слева и справа от этой цифры записаны хорошие числа (число справа, возможно, начинается с нуля), в каждом из них используется не более $k$ различных цифр, поэтому в каждом из них (по индукции) не более $2^k – 1$ знаков, а суммарно в $X$ тогда не более $(2^k – 1) + (2^k – 1) + 1 = 2^{k+1} – 1$ знаков, что и требовалось.
Пример хорошего числа, содержащего $k$ различных цифр $(1 \leqslant k \leqslant 10)$, в записи которого ровно $2^k – 1$ знаков, также построим по индукции.
База ($k=1$): годится число $1$ (берём не $0$, чтобы далее итоговое число не начиналось с $0$).
Шаг индукции. Пусть $1 \leqslant k \leqslant 9$ и $X$ – хорошее число, в котором $k$ различных цифр и $2^k – 1$ знаков. Возьмём цифру, которая не встречается в этом числе (назовём её $a$), и припишем к ней слева и справа число $X$. В полученном числе $2^{k+1} – 1$ знаков, и оно хорошее: ведь любая его часть из несколько подряд идущих цифр либо включает единственную в числе цифру $a$, либо является частью хорошего числа $X$.
