Question

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

Answer 1

Если длина группы не ограничена, то максимум - это все 6 разных букв.
То есть ровно весь алфавит.
Седьмую букву, какую бы мы ни поставили, это будет повтор одной из предыдущих букв, а повторов быть не должно.

Answer 2

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

При решении этой задачи можно использовать принцип Дирихле, который гласит, что если n+1 объектов распределить по n ящикам, то хотя бы в одном ящике окажется не менее двух объектов. В данном случае, если мы имеем строку длиной больше 6, то в ней должно быть хотя бы 7 различных букв, иначе в какой-то группе из нескольких последовательных букв некоторая буква встретится бы более одного раза.

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

[[1]]