XVI математическая олимпиада «Шелковый путь», 2021 год

Дана последовательность $s$, состоящая из нулей и единиц. Для каждого натурального $k$ определим $v_k$ как наибольшее количество способов, которыми в какой-нибудь последовательности длины $k$ могут быть выделены несколько последовательных цифр, образующих последовательность $s$. (Например, если $s=0110$, то $v_7=v_8=2$, так как в последовательностях 0110110 и 01101100 найти подряд стоящие цифры 0110 можно в двух местах, а три пары единиц, обрамленных нулями, не могут встретиться в последовательности длины 7 или 8.) Известно, что $v_n < v_{n+1} < v_{n+2}$ для некоторого натурального $n$. Докажите, что в последовательности $s$ все цифры одинаковы. ( А. Голованов )

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

Решение: Заметим, что $v_{m+1}=v_m$ или $v_{m+1}=v_m+1,\forall m\ge 1,$ что легко понять, если рассмотреть первые $m$ элементов последовательности длины $m+1.$

Поэтому из условия следует, что $v_{n+2}=v_{n+1}+1$ и $v_{n+1}=v_{n}+1.$ Рассмотрим последовательность $b$ длины $n+2$ в которой можно выделить $v_{n+2}$ последовательностей $s.$ Рассмотрим первые $n+1$ элементов этой последовательности (назовем этк последовательность $a$). Ясно, что в ней можно выделить не более $v_{n+1}$ последовательностей $s,$ поэтому "конец" последовательности $b$ равен $s.$ Аналогично "конец" последовательности $a$ равен $s.$ Пусть $s=s_1,\ldots,s_p.$ Из ранее доказанного следует, что $s_2=s_1, s_3=s_2, \ldots s_p=s_{p-1},$ ч.т.д. $\blacksquare$