Рассмотрим алфавит из 2 букв. Словом будем считать любое конечное сочетание букв...

November 2021 1 28 Report

Рассмотрим алфавит из 2 букв. Словом будем считать любое конечное сочетание букв. Назовём слово непроизносимым, если в нём встречается больше двух одинаковых букв подряд. На сколько больше произносимых 10 буквенных слов, чем 9-буквенных?

Answers & Comments

Denik777

Verified answer

Произносимые слова - это слова, в которых имеется не более двух одинаковых букв подряд. Пусть алфавит состоит из букв "0" и "1".
Обозначим $F_n$ - количество произносимых слов длины n, начинающихся с 1. Очевидно, количество произносимых слов, начинающихся с 0 также равно $F_n$ (одни получаются из других взаимной заменой 0 и 1). Тогда, если n≥3, то любое произносимое слово длины n, начинающееся с 1, можно получить одним из следующих двух способов:
1) К "1" приставить справа любое произносимое слово длины n-1, начинающееся на 0. Таких слов $F_{n-1}$ штук, причем, полученные слова обязательно будут произносимыми, т.к. начинаются на "10" и не могут содержать три нуля или три единицы подряд.
2) К "11" приставить справа любое произносимое слово длины n-2, начинающееся на 0. Таких слов $F_{n-2}$ штук. Это слово также произносимо, т.к. начинается на 110, и, значит, не содержит трех нулей или единиц подряд.
Итак, $F_{n}=F_{n-1}+F_{n-2}$ и легко видеть, что $F_{1}=1$ ( есть только одно произносимое слово "1" длины 1, начинающееся на "1") и $F_{2}=2$ (есть только два произносимых слова "10" и "11" длины 2, начинающиеся с "1"). Таким образом, количество всех произносимых слов длины n равно равно $2F_n$ и равно удвоенному n-ому числу Фибоначчи. Т.е., начиная с $F_1$ , последовательность $F_n$ имеет вид 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., где каждое следующее число - сумма двух предыдущих.
$F_{10}=89$ , $F_9=55$ , а значит, искомая разность равна
$2(F_{10}-F_9)=2F_8=2\cdot 34=68.$

1 votes Thanks 1

Answers & Comments

Verified answer

kakoe maksimalnoe kolichestvo shashek mozhno rasstavit na doske 7x7 chtoby oni yavl

v meshke lezhat varezhki pravye i levye vsego 12 par 9 krasnyh i 3 sinih mezhdu

srednee garmonicheskoe kvadratichnoe i arifmeticheskoe razlichnyh naturalnyh chisel

summa desyati naturalnyh chisel a1ltlta10 ravna 300 najdite maksimalno v

b.)...

najdite naimenshee tryohznachnoe chislo ravnoe summe svoih cifr umnozhennoj na raz

рекомендуемые вопросы

Helpful Links

Helpful Social