добавил президент любознательной Тускарии.
Веточка на минуту остановилась, подумала, сообразила и продолжала:
— …если все это так, то нам, для того чтобы решить, переходит ли одна позиция в другую, надо подсчитать число инверсий. Если оно четное, то…
— …то и перестановка четная! — помог Веточке дедушка.
— Ну да! Перестановка четная, а следовательно, перестановка такая в Дразнилке возможна. Если инверсий нечетное число, то перестановка нечетная и в Дразнилке ее сделать нельзя.
— А почему именно нельзя? — спросил Ника.
— Очень просто! — ответил ему Вовка. — Возьмем для примера наш бустрофедон у того же среднего Дразнилки, как это показано у нас на чертеже (а черная стрелка — маршрут!).
Если рассматривать бустрофедон как маршрут, — ну вот, как мы маршрут в одночеркальных фигурках рассматривали!—то это один маршрут с двумя нечетными узлами-концами: первый узел в самом начале, второй в самом конце. И вьется такой змейкой слева направо, справа налево и опять слева направо.
Поэтому всякое движение — вперед или назад, все равно! — но вдоль по бустрофедону ничего в позиции не меняет и никаких инверсий не вносит. Сделаем такие ходы:
и никаких инверсий не будет, только нуль-пустышка переберется из нижнею правого угла коробочки в верхний левый. Но если ход делается не вдоль по бустрофедону, а наперерез маршруту, то шашка обходит другие шашки, и получаются инверсии.
— Если взять, — добавил дед, — последние две строки бустрофедона в большом Дразнилке, то шашки в этих двух последних строках
стоят так, как это изображено на нашем чертеже. Ясно, что движение шашек в последней строке не меняет числа инверсий, то есть число инверсий будет равняться нулю, иначе говоря — оно четное. Если мы, следуя маршруту бустрофедона, сделаем
ходы: 15, 14, 13, 12…
то мы откроем нуль в предпоследней строке и убедимся, что и в ней движение шашек по горизонтали не дает инверсий, их снова нуль, снова четное число. Теперь поставим шашки по-прежнему и сделаем два хода:
15, 14…
Если мы теперь сделаем ход наперерез маршруту, то есть пойдем одиннадцатой шашкой, то мы образуем пару инверсий. Это самое малое возможное число инверсий после нуля. Меньше этого уж сделать нельзя, если, конечно, тебе не придет в голову фантазия вынимать шашки из коробочки! Нельзя это сделать потому, что шашки Дразнилки ходят только по прямым на манер шахматной ладьи, но всегда
