Олимпиадная задача по теории чисел с заменами букв
По кругу стоят буквы A и B, всего 41 буква. Можно заменять ABA на B и наоборот, а также BAB на A и наоборот.
Верно ли, что из любого начального расположения можно получить такими операциями круг, на котором стоит ровно одна буква?
Показать ответ
Верно.
Разобрать решение
Разобьём все буквы на группы одинаковых подряд идущих. Количество букв нечётно, поэтому найдётся "нечётная" группа. Заменами сделаем из неё однобуквенную группу, после чего будем удалять соседей этой буквы, пока это возможно. Действуя таким образом, оставим только одну букву.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.