20-шы «Жібек жолы» математикалық олимпиадасы, 2021 жыл

0 және 1 цифрларынан құралған $s$ тізбегі берілген. Кез келген натурал $k$ саны үшін $v_k$ арқылы ұзындығы $k$-ға тең қандай да бір тізбектің қатар келген цифрларынан $s$ тізбегін бөліп алудың ең үлкен тәсіл санын белгілейік. (Мысалға, егер $s=0110$ болса, онда $v_7$ және $v_8$ сандарының ең үлкен мәні $v_7=v_8=2$-ге тең, өйткені 0110110 және 01101100 тізбектерінде қатар келген цифрлардан 0110 тізбегін тек екі жерде ғана табуға болады, бірақ ұзындығы 7 және 8-ге тең ешқандай тізбекте осындай 0110 тізбегі үш жерде кездесе алмайды.) Егер қандай да бір натурал $n$ саны үшін $v_n < v_{n+1} < v_{n+2}$ теңсіздіктері орындалса, онда $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$