Чтобы понять задачу, начнём пробовать с 1 буквы, с двух букв и т.д. Пусть алфавит состоит из одной буквы А. Наибольшая длина требуемой последовательности равна 1, т.е. состоит из 1 буквы А. Пусть алфавит состоит из двух букв А и Б. Тогда требуемая последовательность будет состоять из трёх букв: АБА. Пусть алфавит состоит из трёх букв А, Б и В. Тогда требуемая последовательность будет такая АБАВАБА (7 букв). Т.е. одна буква в середине, а по краям повторяются последовательности, которые были рассмотрены на шаг ранее. И теперь, какую бы последовательность мы не возьмём, одна из букв будет встречаться только один раз. Вырисовывается некая закономерность, поэтому легко составляется последлвательность для алфавита из 4-х букв А, Б, В и Г: АБАВАБАГАБАВАБА (15 букв). Можно таким образом продолжить и далее до алфавита из 7 букв, но заметим, что в последовательности, состоящей из длин требуемой строки, есть закономерность: 1, 3, 7, 15, ... - это не что иное, как , где n - количество букв в алфавите. Значит, для n=7 получим: Покажем, что это распространяется для любого n методом математической индукции. Первые шаги нами уже проверены, поэтому предполагаем, что формула верна для некоего числа n. Докажем, что это выполянется и при (n+1). Что мы делали, когда составляли последовательность, добавляя в алфавит ещё одну букву? Мы брали две предыдущие последовательности и в середину вставляли новую букву. Что и требовалось доказать.
Чтобы понять задачу, начнём пробовать с 1 буквы, с двух букв и т.д. Пусть алфавит состоит из одной буквы А. Наибольшая длина требуемой последовательности равна 1, т.е. состоит из 1 буквы А. Пусть алфавит состоит из двух букв А и Б. Тогда требуемая последовательность будет состоять из трёх букв: АБА. Пусть алфавит состоит из трёх букв А, Б и В. Тогда требуемая последовательность будет такая АБАВАБА (7 букв). Т.е. одна буква в середине, а по краям повторяются последовательности, которые были рассмотрены на шаг ранее. И теперь, какую бы последовательность мы не возьмём, одна из букв будет встречаться только один раз. Вырисовывается некая закономерность, поэтому легко составляется последлвательность для алфавита из 4-х букв А, Б, В и Г: АБАВАБАГАБАВАБА (15 букв). Можно таким образом продолжить и далее до алфавита из 7 букв, но заметим, что в последовательности, состоящей из длин требуемой строки, есть закономерность: 1, 3, 7, 15, ... - это не что иное, как , где n - количество букв в алфавите. Значит, для n=7 получим: Покажем, что это распространяется для любого n методом математической индукции. Первые шаги нами уже проверены, поэтому предполагаем, что формула верна для некоего числа n. Докажем, что это выполянется и при (n+1). Что мы делали, когда составляли последовательность, добавляя в алфавит ещё одну букву? Мы брали две предыдущие последовательности и в середину вставляли новую букву. Что и требовалось доказать.
, где n - количество букв в алфавите. Значит, для n=7 получим:
1% от 6500=0,01*6500=65
1% от 8354=83,54
1% от 68=0,01*68=0,68
1% от 15=0,01*15=0,15
1% от 650000=650000*0,01=6500