Question

В алфавите племени Тумба-Юмба 9 букв. Мистер Фокс хочет выписать их в строку (буквы могут повторяться) так, чтобы в любой группе из нескольких последовательных букв некоторая буква встречалась бы ровно один раз. Какую наибольшую длину может иметь такая строка?

Answer 1

Видимо, только эти 9 букв. Ведь если хоть раз еще одну букву напишет, условие не будет удовлетворяться, если он захочет, к примеру, выбрать последовательность из 10 букв.

Answer 2

Для решения этой задачи можно воспользоваться принципом Дирихле.

Из условия задачи следует, что в любой группе из нескольких последовательных букв должна быть хотя бы одна буква, которая встречается ровно один раз.

Рассмотрим возможные варианты для составления такой строки.

1) Если в алфавите племени Тумба-Юмба есть буква, которая встречается ровно один раз, то такая строка может иметь длину 1.

2) Если все буквы встречаются более одного раза, то в строке не может быть буквы, которая встречается ровно один раз. Поэтому такая строка будет иметь длину 0.

3) Рассмотрим случай, когда в алфавите племени Тумба-Юмба есть буква, которая встречается ровно два раза. В этом случае такая строка может иметь длину 2. Пример такой строки: "AB".

4) Если в алфавите племени Тумба-Юмба есть буква, которая встречается ровно три раза, то такая строка может иметь длину 3. Пример такой строки: "ABC".

5) Если в алфавите племени Тумба-Юмба есть буква, которая встречается ровно четыре раза, то такая строка может иметь длину 4. Пример такой строки: "ABCD".

И так далее. Максимальная длина строки будет достигаться, когда в алфавите племени Тумба-Юмба есть буква, которая встречается наибольшее количество раз. Поэтому максимальная длина такой строки будет равна 9 (количество букв в алфавите племени Тумба-Юмба).

Таким образом, наибольшая длина такой строки равна 9.