Задача 66848

Темы:    [ Теория алгоритмов (прочее) ] [ Четность и нечетность ]

Сложность: 3+ Классы: 8,9,10,11

Условие

Автор: Дидин М.

По кругу стоят буквы A и B, всего 41 буква. Можно заменять ABA на B и наоборот, а также BAB на A и наоборот.
Верно ли, что из любого начального расположения можно получить такими операциями круг, на котором стоит ровно одна буква?

Решение

Разобьём все буквы на группы одинаковых подряд идущих. Количество букв нечётно, поэтому найдётся "нечётная" группа. Заменами  $AA \longleftrightarrow BABA \longleftrightarrow BB$  сделаем из неё однобуквенную группу, после чего будем удалять соседей этой буквы, пока это возможно. Действуя таким образом, оставим только одну букву.

Ответ

Верно.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
номер/год
Номер	41
Год	2019/20
неизвестно
Вариант	весенний тур, базовый вариант, 10-11 класс
задача
Номер	3