Назад
Задача

Для какого наибольшего $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$.

Ответ

Для $N = 2^{10}$ – 1 = 1023.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет