Олимпиада имени Леонарда Эйлера2013-2014 учебный год, II тур заключительного этапа

Десятичная запись натурального числа $N$ составлена только из единиц и двоек. Известно, что вычёркиванием цифр из этого числа можно получить любое из 10000 чисел, состоящих из 9999 единиц и одной двойки. Найдите наименьшее возможное количество цифр в записи числа $N$. ( Г. Челноков )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 10198.
Решение. Пример. Число $1 \dots 121 \dots 12 \dots 21 \dots 121 \dots 1$, где 100 двоек, спереди и сзади — по 99 единиц, а между соседними двойками — по 100 единиц. Число из 9999 единиц и двойки, где перед двойкой идет $100m+n$ единиц $(0 \leq m,n \leq 99)$ получается вычеркиванием всех двоек, кроме $(m+1)$-ой, $99 -n$ единиц перед ней и $n$ единиц за ней.
Оценка.Заметим, что в числе $N$ нет двух двоек, идущих подряд — иначе его можно укоротить, вычеркнув одну из этих двоек. Пусть в числе $N$ $k$ двоек, перед первой двойкой идут $a_0$ единиц, между первой и второй — $a_1$ единиц, $\dots$ , после последней двойки — $a_k$ единиц. Положим $s = a_0+ \dots +a_k$. Для получения числа, у которого перед двойкой одна единица, нам придется вычеркнуть не меньше $a_0 -1$ единиц. Поэтому число $s -(a_0 -1)$ должно быть не меньше 9999, то есть $s -a_0 \geq 9998$. Для получения числа, у которого перед двойкой $a_0+1$ единица, придется вычеркнуть первую двойку и не меньше $a_1 -1$ единиц, откуда получаем неравенство $s -a_1 \geq 9998$. Для получения числа, у которого перед двойкой $a_0+a_1+1$ единица, придется вычеркнуть две первых двойки и не меньше $a_2 - 1$ единиц, откуда получаем неравенство $s - a_2 \geq 9998$. Рассуждая аналогично, получаем, что неравенство $s -a_i \geq 9998$ выполнено при всех $i$ от 0 до $k -1$; кроме того, для получения числа, где двойка идет последней, требуется, чтобы $s-a_k \geq 9999$. Складывая все эти неравенства, получаем неравенство $(k+1)s - s \geq 9998(k+1)+1 \Rightarrow ks > 9998(k+1) \Rightarrow s > 9998+9998/k$. Так как в искомом числе ещё и $k$ двоек, количество цифр в нем больше, чем $9998+9998/k+k \geq 9998+2\sqrt{9998} > 10197$, что и требовалось доказать.