Изначально в строку выписывают 250 букв — 125 букв А и 125 букв Б в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв А и Б, и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы А на буквы Б и буквы Б на буквы А. (Например, из строки АБАББАА | {z} Б можно одной операцией получить строку АББААБА | {z} Б.) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке?
1 Ответ
Решение:
Пронумеруем позиции в строке слева направо числами от 1 до 250. Пусть в исходной строке x букв А стоят на нечётных местах (т. е. местах с нечётными номерами). Покажем, что в полученных строках это количество не изменится. Действительно, пусть для некоторой операции выбран кусок, в котором по y букв А и Б, причём t из этих букв А стоят на нечётных местах. Тогда на чётных местах в куске стоят y − t букв А и, следовательно, y − (y − t) = t букв Б. После операции именно из этих t букв Б возникнут буквы А, стоящие на нечётных местах куска — значит, количество таких букв А не поменяется. Итак, в любой полученной строке будет ровно x букв А на
нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно
125 − x букв А. Поскольку 125 − x 6= x, требуемое невозможно.
Ответ. Нельзя.