ВОЛШЕБНЫЙ ДВУРОГ

Из 2-3-1 в зеркале вышло 1-3-2; из 3-1-2 получилось 2-1-3.

- Ну, как ты думаешь, - спросил Радикс, - можно ли уложить карточки так, чтобы и перед зеркалом и в зеркале получилось одно и то же расположение?

- Н-нет, - сказал в недоумении Илюша. - Ну как же это возможно? Нет, нельзя!

- Так, - отвечал его наставник, - Значит, там один круг, а здесь другой. Ну, вот и всё. Весь секрет Дразнилки в том, что там при наличии одной пустышки, в сущности, возможны только круговые перестановки. Игра в Дразнилку, как ты и сам понимаешь, это игрушка, почти безделка, но вот именно из-за того, что в этой игре участвуют эти круговые перестановки, о которых мы еще наговоримся впоследствии, игрушка эта получает довольно серьезный смысл. А перевести 1-2-3 в 3-2-1 циклической перестановкой нельзя, как нельзя добиться, чтобы в зеркале было то же, что перед зеркалом. Значит, если у тебя стоит с самого начала какая-нибудь комбинация из круга "А", то ты можешь прийти к основной комбинации 1-2-3.

- 102 -

Это будет четный круг. Но если у тебя стоит комбинация из круга "Б", то ее перевести в основную комбинацию невозможно. Но это - круг нечетный. Попробуй теперь в основной комбинации 1-2-3 переставить две какие-нибудь рядом стоящие цифры.

Илюша переставил. Из 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 -