Question

В алфавите инопланетян две буквы: Ки А. Б) Сколько 9-буквенных слов можно составить на их языке, если буква К не может встречаться 2 раза подряд? В) Сколько 10-буквенных слов может быть в языке этого племени, если буква К не может встречаться 3 раза подряд? Можно пожалуйста до четверга ответ, ооочень надо

Answer 1

Ответ:

89, 504

Объяснение:

Б) Пусть aК(n) - количество строк длины n, которые оканчиваются на К, и aA(n) - количество строк длины n, которые оканчиваются на А. Очевидно, aK(1) = aA(1) = 1.

Посчитаем, чему равны aK(n + 1) и aA(n + 1).

• К можно дописать к любой строке, которая кончается на А. Поэтому aK(n + 1) = aA(n)
• A можно приписать вообще к любой строке. Значит, aA(n + 1) = aA(n) + aK(n)

Общее количество строк длины n > 2 равно a(n) = aK(n) + aA(n) = aA(n - 1) + a(n - 1) = a(n - 1) + a(n - 2).

Вычисляем значения a(n):

a(1) = 2

a(2) = 3 (АА, АК, КА)

a(3) = 2 + 3 = 5

a(4) = 3 + 5 = 8

a(5) = 5 + 8 = 13

a(6) = 8 + 13 = 21

a(7) = 13 + 21 = 34

a(8) = 21 + 34 = 55

a(9) = 34 + 55 = 89

В последовательности можно увидеть известную последовательность Фибоначчи.

В) Аналогично, введем aA(n), aК(n), aKK(n) - количество строк, оканчивающихся на А, ровно одно К и ровно два К. Общее количество строк будем так же обозначать как a(n).

aA(n + 1) = a(n)

aK(n + 2) = aA(n + 1) = a(n)

aKK(n + 3) = aK(n + 2) = a(n)

Итого, при n > 3 выполнено a(n) = a(n - 1) + a(n - 2) + a(n - 3).

a(1) = 2

a(2) = 4

a(3) = 7 (всего строк длины три 8, не подходит ККК).

a(4) = 2 + 4 + 7 = 13

a(5) = 4 + 7 + 13 =  24

a(6) = 7 + 13 + 24 = 44

a(7) = 13 + 24 + 44 = 81

a(8) = 24 + 44 + 81 = 149

a(9) = 44 + 81 + 149 = 274

a(10) = 81 + 149 + 274 = 504

Если в прошлом случае возникла последовательность Фибоначчи, то тут так называемая последовательность Трибоначчи - каждый новый член равен сумме трёх предыдущих

Answer 2

Для первого вопроса, если буква К не может встречаться 2 раза подряд, то можно рассмотреть несколько случаев:

1) Слова, в которых буква К не встречается. В данном случае мы можем использовать только букву А, и количество таких слов будет равно количеству всех возможных комбинаций из 9 букв без буквы К, то есть 2^9 = 512.

2) Слова, в которых буква К встречается 1 раз. В данном случае мы можем использовать букву А и одну букву К. Количество таких слов будет равно произведению количества всех возможных комбинаций из 8 букв без буквы К (2^8) на количество позиций, на которых может находиться буква К (9), то есть 2^8 * 9 = 4608.

3) Слова, в которых буква К встречается 2 раза, но не подряд. В данном случае мы можем использовать букву А, две буквы К и одну из оставшихся 8 букв. Количество таких слов будет равно произведению количества всех возможных комбинаций из 7 букв без буквы К (2^7) на количество позиций, на которых могут находиться буквы К (C(9,2) = 36), то есть 2^7 * 36 = 4608.

Таким образом, общее количество 9-буквенных слов на языке инопланетян, где буква К не может встречаться 2 раза подряд, будет равно сумме результатов из пунктов 1, 2 и 3: 512 + 4608 + 4608 = 9728 слов.

Для второго вопроса, если буква К не может встречаться 3 раза подряд, можно рассмотреть аналогичные случаи:

1) Слова, в которых буква К не встречается. В данном случае мы можем использовать только букву А, и количество таких слов будет равно количеству всех возможных комбинаций из 10 букв без буквы К, то есть 2^10 = 1024.

2) Слова, в которых буква К встречается 1 раз. Аналогично первому вопросу, количество таких слов будет равно 2^9 * 10 = 5120.

3) Слова, в которых буква К встречается 2 раза, но не подряд. Аналогично первому вопросу, количество таких слов будет равно 2^8 * C(10,2) = 2^8 * 45 = 11520.

4) Слова, в которых буква К встречается 3 раза, но не подряд. В данном случае мы можем использовать букву А, три буквы К и одну из оставшихся 6 букв. Количество таких слов будет равно 2^7 * C(9,3) = 2^7 * 84 = 21504.

Таким образом, общее количество 10-буквенных слов на языке инопланетян, где буква К не может встречаться 3 раза подряд, будет равно сумме результатов из пунктов 1, 2, 3 и 4: 1024 + 5120 + 11520 + 21504 = 39488 слов.