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

186

215

Посмотреть ответы 2

Ответы на вопрос:

shasherina13ozz1hj

Математика

4,5(67 оценок)

Чтобы понять , начнём пробовать с 1 буквы, с двух букв и т.д. пусть алфавит состоит из одной буквы а. наибольшая длина требуемой последовательности равна 1, т.е. состоит из 1 буквы а. пусть алфавит состоит из двух букв а и б. тогда требуемая последовательность будет состоять из трёх букв: аба. пусть алфавит состоит из трёх букв а, б и в. тогда требуемая последовательность будет такая абаваба (7 букв). т.е. одна буква в середине, а по краям повторяются последовательности, которые были рассмотрены на шаг ранее. и теперь, какую бы последовательность мы не возьмём, одна из букв будет встречаться только один раз. вырисовывается некая закономерность, поэтому легко составляется последлвательность для алфавита из 4-х букв а, б, в и г: абавабагабаваба (15 букв). можно таким образом продолжить и далее до алфавита из 7 букв, но заметим, что в последовательности, состоящей из длин требуемой строки, есть закономерность: 1, 3, 7, 15, - это не что иное, как , где n - количество букв в алфавите. значит, для n=7 получим: покажем, что это распространяется для любого n методом индукции. первые шаги нами уже проверены, поэтому предполагаем, что формула верна для некоего числа n. докажем, что это выполянется и при (n+1). что мы делали, когда составляли последовательность, добавляя в алфавит ещё одну букву? мы брали две предыдущие последовательности и в середину вставляли новую букву. что и требовалось доказать. ответ: 127