Даны две последовательности из букв А и Б, в каждой из которых по \(100\) букв. За одну операцию разрешается или вставить в какое-то место последовательности (возможно, в начало или в конец) любое количество одинаковых букв, или убрать из последовательности любое количество подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за \(100\) операций.

Решение

Сначала решим аналогичную задачу для последовательностей из двух букв, а именно докажем, что из одной последовательности можно получить другую не более чем за \(2\) операции.

Если одна из последовательностей \(-\) это АА, а другая \(-\) ББ, уберём все буквы первой последовательности, а затем добавим буквы второй последовательности. В противном случае в последовательностях есть одинаковые буквы (возможно, стоящие на разных местах). Оставим в первой последовательности эту букву, а другую уберём. Затем добавим в нужное место букву, которой недостаёт для второй последовательности. Вернёмся к первоначальной задаче. Разобьём каждую последовательность на \(50\) пар подряд идущих букв. За две операции каждую пару первой последовательности можно переделать в соответствующую пару второй последовательности.