МОШ 2023, 9 класс, задача 2

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

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

Вернёмся к первоначальной задаче. Разобьём каждую последовательность на пар подряд идущих букв. За две операции каждую пару первой последовательности можно переделать в соответствующую пару второй последовательности.

Решение 2. Разобьём каждую из последовательностей на блоки подряд идущих одинаковых букв. В обеих последовательностях получится не более блоков из букв и не более блоков из букв . Если получилось ровно по блоков, то в обеих последовательностях буквы чередуются. Тогда либо последовательности совпадают, либо из первой можно получить вторую, отбросив первую букву и приписав такую же букву в конец.

Пусть в какой-то из последовательностей блоков из какой-то буквы не более . Понятно, что если из второй последовательности с помощью операций можно получить первую, то, проделав операции в обратном порядке, получим из первой последовательности вторую. Поэтому, не умаляя общности, можно считать, что в первой последовательности не более блоков из букв . Проделаем с первой последовательностью следующие операции.

1. Уберём все буквы . На это потребуется не более операций.

2. При необходимости изменим количество букв так, чтобы их количество совпало с количеством букв во второй последовательности. На это потребуется не более операции.

3. Добавим в нужные места блоки из букв , равные по длине соответствующим блокам букв из второй последовательности. На это потребуется не более операций.

В итоге вторая последовательность получена не более чем за операций.

Решение 3. Докажем, что на самом деле можно справиться за не более чем операцию. Как и в предыдущем решении, будем пользоваться тем, что если из второй последовательности можно получить первую, то можно и наоборот.

Пусть буква встречается в первой и второй последовательностях соответственно и раз, а буква — соответственно и раз. Без ограничения общности будем считать, во-первых, что (иначе можно поменять местами буквы), а во-вторых, что (иначе можно поменять местами последовательности). Процесс перевода первой последовательности во вторую выполним в два этапа:

1. удалим из первой последовательности букв , чтобы их стало столько же, сколько во второй последовательности;

2. в полученной последовательности изменим количества букв , стоящих между буквами , чтобы она совпала со второй.

Второй этап можно выполнить за не более чем операцию. Действительно, на обе последовательности (полученную после первого этапа и требуемую) можно смотреть как на последовательности из букв , в промежутках между которыми вставлены ноль или более букв ; всего промежутков ровно (позиции до и после крайних букв тоже считаются «промежутками»). Ясно, что мы можем за не более чем одну операцию привести количество букв , стоящих в каком-то одном промежутке, к требуемому. Значит, за не более чем операцию мы можем «исправить» все количества букв на те, что должны быть в требуемой последовательности.

Осталось доказать, что первый этап можно выполнить за операций.

Отметим, что , так как . При этом если , то из и имеем и . В этом случае первая стадия процесса тривиальна — ничего удалять не нужно. Далее разбираем случай .

Буквы в первой последовательности разделяют буквы на непрерывных блоков из нуля или более букв (считаем, что блок из нуля букв образуется, если две буквы стоят рядом, либо если буква стоит с краю последовательности). Достаточно доказать, что можно выбрать не более чем блоков так, чтобы суммарно в них было не менее букв ; в этом случае мы за не более чем операций можем произвольно уменьшить или удалить эти блоки и добиться требуемого количества букв . Отметим, что если , то можно просто выбрать все блоки, и в них окажется букв ; далее разбираем случай .

Предположим противное: даже если выбрать наибольших (по количеству букв) блоков, в них суммарно окажется не более букв . Заметим, что хотя бы один из выбранных блоков содержит не более одной буквы по принципу Дирихле, так как

Так как мы выбрали наибольшие блоки, то остальные блоков тоже содержат не более чем по одной букве ; суммарно в первой последовательности оказывается не более

букв . Но мы знаем, что их , откуда .

В этом случае ; снова применяя принцип Дирихле, получаем, что один из выбранных блоков содержит ноль букв . Тогда все остальные блоки тоже содержат ноль букв . Следовательно, общее количество букв в первой последовательности не превосходит ; но мы знаем, что их ровно , противоречие.

Замечание. Можно понять, что, например, последовательность нельзя перевести в менее чем за операцию. Действительно, в первой последовательности ноль блоков из букв , а во второй их . При это каждая операция увеличивает количество блоков не более чем на . А ещё должна быть хотя бы одна операция, уменьшающая количество букв , и такая операция не может увеличивать количество блоков из букв .