Волшебный двурог - Страница 34

Илюша переставил. Из 1-2-3 получилось 1-3-2, потому что он переставил 2 и 3.

— Вот теперь получился круг «Б».

— Переставь еще двух соседей.

Илюша поменял местами 3 и 1 и получил 3-1-2.

— А теперь получился круг «А».

— Ну, вот и всё! — сказал Радикс. — Ты, я думаю, и сам видишь, что если переставляешь соседей четное число раз, то получается тот же круг. А если переставишь нечетное число раз любых соседей, причем неважно — этих ли самых или каких-нибудь других, то ты переводишь все расположение во второй круг, и тогда вернуться к первому кругу, не вынимая шашек из коробочки, невозможно. А теперь возьмем какую-нибудь комбинацию шашек в самом маленьком Дразнилке. Ответь мне: можно ли сказать сразу, выйдет у тебя в данном случае или не выйдет?

— Сказать я могу, — отвечал мальчик, — потому что помню, какие комбинации относятся к какому кругу.

— Та-ак… — довольно кисло протянул Радикс. — Однако не в числе шашек дело, потому что всего интереснее располагать правилом, которое было бы пригодно для любого числа шашек. Разумеется, мы начнем с того, что выясним, какие комбинации относятся к какому кругу, но в дальнейшем нам придется рассуждать уже по-иному. Не так ли? Как тебе кажется?

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

— Так. Ну и что же?

— По-моему, можно так рассуждать. Каждый раз я меняю местами две шашки, то есть одну пару. Значит, надо сосчитать, сколько есть таких пар, которые поменялись местами.

Так как я не знаю, как именно они переставлялись, то надо пересмотреть все пары, которые стоят не в том порядке, который нужен. Вот, например, я начинаю с комбинации 1-2-3, затем идет комбинация 2-1-3. Тут только одна пара нарушает порядок: единица и двойка.

— Можно сказать, — вставил Радикс, — что эта пара образует беспорядок, инверсию.

— 103 —

— Хорошо. Значит, у нас здесь одна инверсия. Каждую пару я буду считать только один раз. Дальше беру комбинацию 2-3-1. Здесь есть две пары, образующие инверсии. Первая пара — единица и двойка, вторая — единица и тройка.

Двойка и тройка стоят относительно друг друга в порядке. Значит, здесь две инверсии. Беру еще одну комбинацию: 3-2-1. Здесь три пары шашек нарушают порядок. Первая пара — тройка и двойка. Вторая пара — тройка и единица. Третья пара — двойка и единица. Всего здесь три инверсии. Как ты и говорил, при четном количестве инверсий задачка решается…

— А если нет ни одной?

— Если нет ни одной, то и делать нечего, все и так в порядке. Значит, нуль тоже можно считать четным числом.

— Правильно.

— А если нечетное число инверсий, то задачка не может быть решена. Если подсчитать число инверсий в любой комбинации, то можно сразу сказать, выйдет или не выйдет. Если инверсий четное число, то выйдет; если нечетное, то не выйдет.

— Хорошо, — сказал Радикс, — а теперь перейдем к большому Дразнилке. Как там надо считать число инверсий и какой установить порядок?

Илюша задумался.

— Да, — промолвил он, — они просто по кругу не располагаются. Это ясно. Сейчас я попробую во всем разобраться. Ты не торопи меня. Ага, кажется, я начинаю кое-что понимать.

Начальный порядок там идет змейкой (верхний рисунок).

— Правильно. Так вот мы и будем далее считать, «змейку» как нормальное начальное расположение в Дразнилке. Если двигаться по «змейке», то инверсий не получится. Вдоль нашей «змейки» мы и будем отсчитывать число инверсий. Теперь посмотрим, как вообще будет изменяться число инверсий, если

— 104 —

мы возьмем какое-нибудь — любое — расположение (рисунок средний) и в нем передвинем на пустое место (оно у нас во втором столбце и во второй строке) одну из шашек той же строки, то есть «три» или «восемь».

— Если идти вдоль по «змейке», — отвечал внимательный Илюша, — то число инверсий не изменится. Только разрыв в «змейке», который образует пустышка, перейдет на другое место, а в остальном расположение останется такое же.

— Прелестно! — отметил Радикс. — Ну, а если я на это место подвину одну из шашек того же столбца, то есть «десять» или «шесть», тогда что случится?

— Можно сосчитать! — сказал Илюша. — В первом случае мы перейдем к положению нижнего рисунка, то есть от ряда (по «змейке»)

1, 10, 15, 14, 12, 8, —, 3

к ряду

1, — , 15, 14, 12, 8, 10, 3.

Раньше «десять» образовывало инверсию с «восемью», а теперь этого не будет, но зато появятся инверсии «пятнадцати», «четырнадцати» и «двенадцати» с «десятью»; в общем, окажется на три инверсии больше и на одну меньше — в итоге на две инверсии больше. Если же передвинуть не «десять», а «шесть», то в средних строчках вместо ряда мы получим ряд

12, 8, —, 3, 11, 6, 7, 5

мы получим ряд

12, 8, 6, 3, 11, — , 7, 5;

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

— Вообще, — сказал Радикс, — где бы ты ни оставил пустышку, каждый раз, когда на ее место подвинешь соседнюю шашку сверху или снизу, число инверсий или вовсе не изменится, или изменится на четное число.