Леонард Эйлер атындағы олимпиада,2013-2014 оқу жылы, қорытынды кезеңнің 2-ші туры

Натурал $N$ санның ондық жүйедегі жазуы тек «1» және «2» деген цифрлардан құралған. Осы санның цифрларын өшіру арқылы, 9999 «1» және бір «2» цифрларынан құралған 10000 санның кез келгенін алуға болады. $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$, что и требовалось доказать.