20-я Международная Жаутыковская олимпиада по математике, 2024 год

Әліппе $n$ әріптен құралған. Буын деп кез келген екі әріптен құралған реттелген әріптер жұбын айтайық (мұнда сол екі әріп әртүрлі болуы міндетті емес). Кейбір буындар әдепсіз болып келеді. Сөз деп, құрамында әдепсіз буыны жоқ, кез келген әріптер тізімін айтамыз (әрптер саны шекті немесе шексіз болуы мүмкін). Кемінде неше әдепсіз буын санында ұзындығы шексіз болатын сөз табылмайды? ( М. Карпук )

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

Типо если ab и ba обычеый то будет бесконечно abababa...

Потому хотя бы

один из них не приличный.аа тоже так как будет бесконечно ааа...

Значит там n+n(n-1)/2

Ответ: $\boxed{n+\frac{n(n-1)}{2}.}$

Оценка: Понятно то что у нас есть слоги где две буквы одинаковые (их $n$), а так же слоги где две буквы разные (их $n(n-1)$). Заметим что, у нас всегда должны быть в арсенале слоги с одинаковыми буквами, в другом исходе контр примером было бы бесконечное слово из одной буквы.

Теперь обратим внимание на слоги с разными буквами, если у нас не будет хотя бы половины из них, то найдется какая та пара где будут разрешены оба слога по типу $AB, BA$, соответственно контр примером будет $ABABABA...$, доказано.

Пример: Забаним следующие слоги: $A_iA_i, i=1,2,...,n$ ($n$ штук), и потом выберем первую букву $A_1$, пусть любая комбинация $A_1A_i, i=2,3,...,n$ будет забанена. Выберем $A_2$, пусть любая комбинация $A_2A_i, i=3,4,...,n$ будет забанена, повторяем так до вплоть $A_{n-1}$ - в итоге баним $(n-1)+(n-2)+...+1= \frac{n(n-1)}{2}$ слогов, по ответу все сходится.

Давайте теперь попробуем начать бесконечное слово. Оно не может начаться с $A_1$, после него никакую букву нельзя вставить, ибо все они будут давать забаненные слоги xD. Будем считать что $A_1$ - гибельный, то есть ведёт к тому что слово не будет бесконечным.

Попробуем поставить $A_2$, после него можно поставить только $A_1$, но он гибельный, так что $A_2$ - гибельный.

Поставим $A_3$, после него можно поставить либо $A_1$, либо $A_2$, но они оба гибельные, откуда и появляется гибельность $A_3$. Далее, все работает аналогично.