ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 67184
УсловиеДаны две последовательности из букв А и Б, в каждой из которых по 100 букв. За одну операцию разрешается вставить в какое-то место последовательности (возможно, в начало или в конец) одну или несколько одинаковых букв или убрать из последовательности одну или несколько подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за 100 операций.Решение 1Сначала решим аналогичную задачу для последовательностей из двух букв, а именно докажем, что из одной последовательности можно получить другую не более чем за 2 операции.Если одна из последовательностей — это АА, а другая — ББ, то уберём все буквы первой последовательности, а затем добавим буквы второй последовательности. В противном случае в последовательностях есть одинаковые буквы (возможно, стоящие на разных местах). Оставим в первой последовательности эту букву, а другую уберём. Затем добавим в нужное место букву, которой недостаёт для второй последовательности.
Вернёмся к первоначальной задаче. Разобьём каждую последовательность на 50 пар подряд идущих букв. За две операции каждую пару первой последовательности можно переделать в соответствующую пару второй последовательности. Решение 2Разобьём каждую из последовательностей на блоки подряд идущих одинаковых букв. В обеих последовательностях получится не более 50 блоков из букв А и не более 50 блоков из букв Б. Если получилось ровно по 50 блоков, то в обеих последовательностях буквы чередуются. Тогда либо последовательности совпадают, либо из первой можно получить вторую, отбросив первую букву и приписав такую же букву в конец.Пусть в какой-то из последовательностей блоков из какой-то буквы не более 49. Понятно, что если из второй последовательности с помощью операций можно получить первую, то, проделав операции в обратном порядке, получим из первой последовательности вторую. Поэтому, не умаляя общности, можно считать, что в первой последовательности не более 49 блоков из букв А. Проделаем с первой последовательностью следующие операции.
1. Уберём все буквы A. На это потребуется не более 49 операций.
В итоге вторая последовательность получена не более чем за 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$ букв А, чтобы их стало столько же, сколько во второй последовательности;
Второй этап можно выполнить за не более чем $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$. А ещё должна быть хотя бы одна операция, уменьшающая количество букв А, и такая операция не может увеличивать количество блоков из букв Б. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |