Каждый день в 8:00 Петя выписывает на доску букву или . Затем каждую минуту он делает одно из следующих действий: приписывает сразу после буквы букву ; приписывает сразу перед буквой букву ; приписывает сразу после буквы ещё одну букву ; стирает букву и

Добавлена: 30.04.2026
Обновлена: 30.04.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория графов

Каждый день в 8:00 Петя выписывает на доску букву или . Затем каждую минуту он делает одно из следующих действий: приписывает сразу после буквы букву ; приписывает сразу перед буквой букву ; приписывает сразу после буквы ещё одну букву ; стирает букву и

Условие:

Каждый день в 8:00 Петя выписывает на доску букву $a, b$ или $c$ . Затем каждую минуту он делает одно из следующих действий:

приписывает сразу после буквы $a$ букву $c$ ; приписывает сразу перед буквой $b$ букву $c$ ; приписывает сразу после буквы $c$ ещё одну букву $c$ ; стирает букву $c$ и вписывает на том же месте комбинацию $b a$ . Через 13 минут, получив последовательность из 14 букв, Петя останавливается. Сколько различных последовательностей из 14 букв, в которых ровно 2 буквы $c$ , может получить Петя?

Решение:

Начнём с описания процесса. Каждый день Петя начинает с одной буквы, которую он пишет в 8:00. Затем за 13 минут Петя совершает 13 операций, каждая из которых добавляет ровно одну букву (либо добавляет букву c, либо посредством замены буквы c на пару «b a»).

Заметим, чему равен итоговый размер последовательности: начнём с 1 буквы, за 13 операций прибавляется 13 букв, получаем 14 букв.

Рассмотрим, как меняется число букв c. Пусть обозначим операцию, которая добавляет букву c (операции «приписать c» после a или перед b, или после c) за +1, а операцию D («стереть c и в...