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$. Далее, все работает аналогично.