Архимедово лето. Глава восьмая.

добавил президент любознательной Тускарии.

Веточка на минуту остановилась, подумала, сообразила и продол­жала:

— …если все это так, то нам, для того чтобы решить, переходит ли одна позиция в другую, надо подсчитать число инверсий. Если оно четное, то…

— …то и перестановка четная! — помог Веточке дедушка.

— Ну да! Перестановка четная, а следовательно, перестановка такая в Дразнилке возможна. Если инверсий нечетное число, то пере­становка нечетная и в Дразнилке ее сделать нельзя.

— А почему именно нельзя? — спросил Ника.

— Очень просто! — ответил ему Вовка. — Возьмем для примера наш бустрофедон у того же среднего Дразнилки, как это показано у нас на чертеже (а черная стрелка — маршрут!).

clip_image034

Если рассматривать бустрофедон как маршрут, — ну вот, как мы маршрут в одночеркальных фигурках рассматривали!—то это один маршрут с двумя нечетными узлами-концами: первый узел в самом начале, второй в самом конце. И вьется такой змейкой слева направо, справа налево и опять слева направо.

Поэтому всякое движение — вперед или назад, все равно! — но вдоль по бустрофедону ничего в позиции не меняет и никаких инверсий не вносит. Сделаем та­кие ходы:

и никаких инверсий не будет, только нуль-пустышка переберется из нижнею правого угла коробочки в верхний левый. Но если ход де­лается не вдоль по бустрофедону, а наперерез маршруту, то шашка обходит другие шашки, и получаются инверсии.

— Если взять, — добавил дед, — последние две строки бустрофедона в большом Дразнилке, то шашки в этих двух последних строках

clip_image036

стоят так, как это изображено на нашем чертеже. Ясно, что движение шашек в последней строке не меняет числа инверсий, то есть число инверсий бу­дет равняться нулю, иначе говоря — оно четное. Если мы, следуя маршруту бустрофедона, сделаем

ходы: 15, 14, 13, 12…

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

15, 14…

Если мы теперь сделаем ход наперерез маршруту, то есть пойдем одиннадцатой шашкой, то мы образуем пару инверсий. Это самое малое возможное число инверсий после нуля. Меньше этого уж сде­лать нельзя, если, конечно, тебе не придет в голову фантазия выни­мать шашки из коробочки! Нельзя это сделать потому, что шашки Дразнилки ходят только по прямым на манер шахматной ладьи, но всегда

Страница 11 of 36« First...10...1112...2030...Last »
Category: Разное