Чтение онлайн

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

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

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

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

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

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

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

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

– 103 -

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

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

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

– Если нет ни одной, то и делать нечего, все и так в порядке.

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

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

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

– Да, - промолвил он, - они просто по кругу не располагаются.

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

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

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

Теперь посмотрим, как вообще будет изменяться число инверсий, если мы возьмем какое-нибудь - любое - расположение (рисунок средний) и в нем передвинем на пустое место (оно у нас во втором столбце и во второй строке) одну из шашек той же строки, то есть "три" или "восемь".

– 104 -

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

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

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

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

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

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

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

12, 8, 6, 3, 11, - , 7, 5:

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

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

< image l:href="#"/>

Большая стрелка показывает, как идет "змейка".

– 105 -

– Да-а, - протянул Илюша.
– Из этих примеров выходит так. Но я не пойму: как надо рассуждать, чтобы убедиться в том, что всегда так будет выходить?

– Ну хорошо!
– примирительно сказал Радикс.
– Давай теперь соберем все наши наблюдения над Дразнилкой. И попробуем подытожить все вместе. Итак - шашка может обойти только четное число других шашек: две, четыре и шесть. Это и есть основа всей системы Дразнилки: если есть возможность, комбинируя друг с другом такие четные обходы, достигнуть желаемой позиции - задачка решается. Если нет, то и нет решения. Надо сравнить заданную позицию с желаемой: если между ними четное число инверсий - все в порядке! Если нечетное, ничего добиться нельзя. Вот и все! Любая позиция из круга иной четности переходит в обратный круг при перестановке с места на место одной-единственной (но не двух!) шашки. Если внимательно посмотреть на зеркальное отображение самого маленького трехшашечного Дразнилки, то ясно, что один круг переходит в другой как раз через зеркальное отображение. Но если это так, то всегда из задачи, которая "не выходит", можно сделать другую, которая "выходит". Это будет та же искомая позиция, но в зеркальном отображении.