ВсОШ 2023, 9 класс, задача 2
( баллов) Изначально в строку выписывают букв — букв и букв в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв и , и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы на буквы и буквы на буквы . (Например, из строки можно одной операцией получить строку .) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке? (С. Берлов)
Ответ
Ответ. Нельзя.
Первое решение. Пронумеруем позиции в строке слева направо числами от до . Пусть в исходной строке букв стоят на нечётных местах (т. е. местах с нечётными номерами). Покажем, что в полученных строках это количество не изменится. Действительно, пусть для некоторой операции выбран кусок, в котором по букв и , причём из этих букв стоят на нечётных местах. Тогда на чётных местах в куске стоят букв и, следовательно, букв . После операции именно из этих букв возникнут буквы , стоящие на нечётных местах куска — значит, количество таких букв не поменяется. Итак, в любой полученной строке будет ровно букв на нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно букв . Поскольку , требуемое невозможно.
Замечание. В решении выше предъявлен инвариант процесса (то есть величина, остающаяся постоянной) — количество букв на нечётных местах. Существуют и другие похожие инварианты, позволяющие решить задачу. Например, можно показать, что сумма номеров мест, на которых стоят буквы , является таким инвариантом.
Второе решение. Предъявим ещё один инвариант. В строке всего пар, состоящих из буквы и буквы . Назовём такую пару левой, если в ней стоит левее , и правой иначе. Покажем, что при операции количество левых пар не изменяется. Из этого будет следовать невозможность требуемого, ибо при развороте строки все пары меняют тип, а значит, количество левых пар меняет чётность. Рассмотрим одну операцию с куском длины . При этой операции пары из букв, не лежащих в куске, сохраняют свой тип. Далее, для каждой буквы вне куска было ровно пар, содержащих её и букву из куска; столько же таких пар осталось, и все эти пары были и стали одного и того же типа. Значит, осталось проследить за парами букв в самом куске. Но каждая пара сменила свой тип дважды: когда кусок развернулся и когда все буквы заменили на другие. Значит, количество левых пар в куске также не изменилось.
Замечание. Можно показать, что по количеству левых пар восстанавливается сумма номеров мест букв (и наоборот). Таким образом, инвариант в этом решении — тот же, что и в предыдущем замечании.