|
|
 |
Условие
Даны две последовательности из букв А и Б, в каждой из которых по 100 букв. За одну операцию разрешается вставить в какое-то место последовательности (возможно, в начало или в конец) одну или несколько одинаковых букв или убрать из последовательности одну или несколько подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за 100 операций.Решение 1
Сначала решим аналогичную задачу для последовательностей из двух букв, а именно докажем, что из одной последовательности можно получить другую не более чем за 2 операции.Если одна из последовательностей — это АА, а другая — ББ, то уберём все буквы первой последовательности, а затем добавим буквы второй последовательности. В противном случае в последовательностях есть одинаковые буквы (возможно, стоящие на разных местах). Оставим в первой последовательности эту букву, а другую уберём. Затем добавим в нужное место букву, которой недостаёт для второй последовательности.
Вернёмся к первоначальной задаче. Разобьём каждую последовательность на 50 пар подряд идущих букв. За две операции каждую пару первой последовательности можно переделать в соответствующую пару второй последовательности.
Решение 2
Разобьём каждую из последовательностей на блоки подряд идущих одинаковых букв. В обеих последовательностях получится не более 50 блоков из букв А и не более 50 блоков из букв Б. Если получилось ровно по 50 блоков, то в обеих последовательностях буквы чередуются. Тогда либо последовательности совпадают, либо из первой можно получить вторую, отбросив первую букву и приписав такую же букву в конец.Пусть в какой-то из последовательностей блоков из какой-то буквы не более 49. Понятно, что если из второй последовательности с помощью операций можно получить первую, то, проделав операции в обратном порядке, получим из первой последовательности вторую. Поэтому, не умаляя общности, можно считать, что в первой последовательности не более 49 блоков из букв А. Проделаем с первой последовательностью следующие операции.
1. Уберём все буквы A. На это потребуется не более 49 операций.
2. При необходимости изменим количество букв Б так, чтобы их количество совпало с количеством букв Б во второй последовательности. На это потребуется не более 1 операции.
3. Добавим в нужные места блоки из букв А, равные по длине соответствующим блокам букв А из второй последовательности. На это потребуется не более 50 операций.
В итоге вторая последовательность получена не более чем за 100 операций.
Решение 3
Докажем, что на самом деле можно справиться за не более чем $51$ операцию. Как и в предыдущем решении, будем пользоваться тем, что если из второй последовательности можно получить первую, то можно и наоборот.Пусть буква А встречается в первой и второй последовательностях соответственно $a_1$ и $a_2$ раз, а буква Б — соответственно $b_1 = 100 - a_1$ и $b_2 = 100 - a_2$ раз. Без ограничения общности будем считать, во-первых, что $a_1 + a_2 \leq 100 \leq b_1 + b_2$ (иначе можно поменять местами буквы), а во-вторых, что $a_1 \geq a_2$ (иначе можно поменять местами последовательности). Процесс перевода первой последовательности во вторую выполним в два этапа:
1) удалим из первой последовательности $a_1 - a_2$ букв А, чтобы их стало столько же, сколько во второй последовательности;
2) в полученной последовательности изменим количества букв Б, стоящих между буквами А, чтобы она совпала со второй.
Второй этап можно выполнить за не более чем $a_2 + 1$ операцию. Действительно, на обе последовательности (полученную после первого этапа и требуемую) можно смотреть как на последовательности из $a_2$ букв А, в промежутках между которыми вставлены ноль или более букв Б; всего промежутков ровно $a_2 + 1$ (позиции до и после крайних букв А тоже считаются «промежутками»). Ясно, что мы можем за не более чем одну операцию привести количество букв Б, стоящих в каком-то одном промежутке, к требуемому. Значит, за не более чем $a_2 + 1$ операцию мы можем «исправить» все количества букв Б на те, что должны быть в требуемой последовательности.
Осталось доказать, что первый этап можно выполнить за $50 - a_2$ операций.
Отметим, что $50 - a_2 \geq 0$, так как $$a_2 = \frac{1}{2} (a_2 + a_2) \leq \frac{1}{2}(a_1 + a_2) \leq 50. $$ При этом если $a_2 = 50$, то из $a_2 \leq a_1$ и $a_1 + a_2 \leq 100$ имеем и $a_1 = 50$. В этом случае первая стадия процесса тривиальна — ничего удалять не нужно. Далее разбираем случай $50 - a_2 > 0$.
Буквы Б в первой последовательности разделяют буквы А на $b_1 + 1$ непрерывных блоков из нуля или более букв (считаем, что блок из нуля букв А образуется, если две буквы Б стоят рядом либо если буква Б стоит с краю последовательности). Достаточно доказать, что можно выбрать не более чем $50 - a_2$ блоков так, чтобы суммарно в них было не менее $a_1 - a_2$ букв А; в этом случае мы за не более чем $50 - a_2$ операций можем произвольно уменьшить или удалить эти блоки и добиться требуемого количества букв А. Отметим, что если $50 - a_2 \geq b_1 + 1$, то можно просто выбрать все блоки, и в них окажется $a_1 \geq a_1 - a_2$ букв А; далее разбираем случай $50 - a_2 < b_1 + 1$.
Предположим противное: даже если выбрать $50 - a_2$ наибольших (по количеству букв) блоков, в них суммарно окажется не более $a_1 - a_2 - 1$ букв А. Заметим, что хотя бы один из выбранных блоков содержит не более одной буквы А по принципу Дирихле, так как $$ a_1 - a_2 - 1 < 2 (50 - a_2) \ \Leftarrow\ a_1 + a_2 < 101 \ \Leftarrow\ a_1 + a_2 \leq 100 .$$ Так как мы выбрали наибольшие блоки, то остальные $$(b_1 + 1) - (50 - a_2)$$ блоков тоже содержат не более чем по одной букве А; суммарно в первой последовательности оказывается не более $$ (a_1 - a_2 - 1) + ( (b_1 + 1) - (50 - a_2)) = a_1 + b_1 - 50 = 50 $$ букв А. Но мы знаем, что их $a_1$, откуда $a_1 \leq 50$.
В этом случае $a_1 - a_2 - 1 < 50 - a_2$; снова применяя принцип Дирихле, получаем, что один из выбранных блоков содержит ноль букв А. Тогда все остальные блоки тоже содержат ноль букв А. Следовательно, общее количество букв А в первой последовательности не превосходит $a_1 - a_2 - 1$; но мы знаем, что их ровно $a_1$, противоречие.
Комментарий. Последовательность ААА...АА нельзя перевести в АБАБ...АБ менее чем за $51$ операцию. Действительно, в первой последовательности ноль блоков из букв Б, а во второй их $50$. При этом каждая операция увеличивает количество таких блоков не более чем на $1$. А ещё должна быть хотя бы одна операция, уменьшающая количество букв А, и такая операция не может увеличивать количество блоков из букв Б.
