Сергей Бобров - ВОЛШЕБНЫЙ ДВУРОГ
Двойка и тройка стоят относительно друг друга в порядке. Значит, здесь две инверсии. Беру еще одну комбинацию: 3-2-1. Здесь три пары шашек нарушают порядок. Первая пара — тройка и двойка. Вторая пара — тройка и единица. Третья пара — двойка и единица. Всего здесь три инверсии. Как ты и говорил, при четном количестве инверсий задачка решается…
— А если нет ни одной?
— Если нет ни одной, то и делать нечего, все и так в порядке. Значит, нуль тоже можно считать четным числом.
— Правильно.
— А если нечетное число инверсий, то задачка не может быть решена. Если подсчитать число инверсий в любой комбинации, то можно сразу сказать, выйдет или не выйдет. Если инверсий четное число, то выйдет; если нечетное, то не выйдет.
— Хорошо, — сказал Радикс, — а теперь перейдем к большому Дразнилке. Как там надо считать число инверсий и какой установить порядок?
Илюша задумался.
— Да, — промолвил он, — они просто по кругу не располагаются. Это ясно. Сейчас я попробую во всем разобраться. Ты не торопи меня. Ага, кажется, я начинаю кое-что понимать.
Начальный порядок там идет змейкой (верхний рисунок){7}.
— Правильно. Так вот мы и будем далее считать, «змейку» как нормальное начальное расположение в Дразнилке. Если двигаться по «змейке», то инверсий не получится. Вдоль нашей «змейки» мы и будем отсчитывать число инверсий. Теперь посмотрим, как вообще будет изменяться число инверсий, если
— 104 —
мы возьмем какое-нибудь — любое — расположение (рисунок средний){8} и в нем передвинем на пустое место (оно у нас во втором столбце и во второй строке) одну из шашек той же строки, то есть «три» или «восемь».
— Если идти вдоль по «змейке», — отвечал внимательный Илюша, — то число инверсий не изменится. Только разрыв в «змейке», который образует пустышка, перейдет на другое место, а в остальном расположение останется такое же.
— Прелестно! — отметил Радикс. — Ну, а если я на это место подвину одну из шашек того же столбца, то есть «десять» или «шесть», тогда что случится?
— Можно сосчитать! — сказал Илюша. — В первом случае мы перейдем к положению нижнего рисунка, то есть от ряда (по «змейке»)
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;
значит, «шесть» перескочит через «три» и «одиннадцать» и будет теперь образовывать новую инверсию с «тремя», потеряв свою старую с «одиннадцатью», — число инверсий совсем не изменится.
— Вообще, — сказал Радикс, — где бы ты ни оставил пустышку, каждый раз, когда на ее место подвинешь соседнюю шашку сверху или снизу, число инверсий или вовсе не изменится, или изменится на четное число.
Большая стрелка показывает, как идет «змейка».
— 105 —
— Да-а, — протянул Илюша. — Из этих примеров выходит так. Но я не пойму: как надо рассуждать, чтобы убедиться в том, что всегда так будет выходить?
— Ну хорошо! — примирительно сказал Радикс. — Давай теперь соберем все наши наблюдения над Дразнилкой. И попробуем подытожить все вместе. Итак — шашка может обойти только четное число других шашек: две, четыре и шесть. Это и есть основа всей системы Дразнилки: если есть возможность, комбинируя друг с другом такие четные обходы, достигнуть желаемой позиции — задачка решается. Если нет, то и нет решения. Надо сравнить заданную позицию с желаемой: если между ними четное число инверсий — все в порядке! Если нечетное, ничего добиться нельзя. Вот и все! Любая позиция из круга иной четности переходит в обратный круг при перестановке с места на место одной-единственной (но не двух!) шашки. Если внимательно посмотреть на зеркальное отображение самого маленького трехшашечного Дразнилки, то ясно, что один круг переходит в другой как раз через зеркальное отображение. Но если это так, то всегда из задачи, которая «не выходит», можно сделать другую, которая «выходит». Это будет та же искомая позиция, но в зеркальном отображении. Конечно, как это в каждом случае сделать — уж вопрос другой (АЛ-1, VIII).
— Понимаю, — сказал Илюша. — Выходит верно, но как-то не очень складно. Ведь должна же быть какая-нибудь общая причина, благодаря которой число инверсий всегда меняется на четное число при скачке через четное число шашек…
— Ишь какой хитрец! — воскликнул, рассмеявшись, Радикс. — Причина-то как раз в том и заключается, что ты перескакиваешь через четное число шашек, а ведь всякое четное число состоит из двоек. А если взять две шашки, то уже мы с тобой установили… Впрочем, можно этого отдельно и не рассматривать. Будем рассуждать так. Пусть шашка перепрыгивает по «змейке» через четное число 2n шашек. Причем есть р шашек, с которыми у нее были инверсии, и q = 2n — р шашек, с которыми инверсий не было. Ясно, что 2n — четное число. Но если это так, то числа р и q, как говорится, одной четности, то есть либо они оба четные, либо оба нечетные, иначе их сумма не могла бы быть четной. Если же я теперь вычту эти два числа одной четности, р и q, друг из друга, то я обязательно получу четное число, так как разность двух четных, как и двух нечетных, чисел неизбежно четная. Можешь проверить, коли тебе не лень. Другими словами, разность двух чисел всегда одинаковой четности с их суммой. Иначе говоря, алгебраическая сумма некоторого числа единиц с любыми знаками всегда будет одной четности с чис-
— 106 —
лом этих единиц. Вот в чем тут сила! Ну, вернемся к нашей задаче. Изложи мне коротко и ясно: что же мы доказали этим рассуждением?
— Мы доказали, что при всякой перестановке шашки на пустое место число инверсий меняется на четное число. Значит, здесь, как и в маленьком Дразнилке, вернуться к исходному положению (то есть к такому, в котором нуль инверсий) можно только из расположения, в котором подсчет вдоль по «змейке» показывает четное число инверсий.
— Великолепно! — отвечал, вздохнувши, чтобы перевести дух, Радикс. — Вот теперь мы можем сказать, что установили необходимое условие того, чтобы Дразнилка вышел. А то, что это условие еще сверх того и достаточное, можно доказать совершенно строго, но мы этим заниматься не будем.
— Ну! — произнес огорченно Илюша. — Это мне не очень нравится. Ведь выходит, что мы только полдела сделали. И, наверно, это самое интересное и есть, потому что мы не получили правила, как приводить шашки в порядок.
— Конечно. Хотя одно общее доказательство вовсе и не должно указывать, как добиться цели скорей всего. Но только дело в том, что это доказательство не простое, и я не уверен, захочешь ли ты его слушать.
— Захочу, захочу! — обиженно сказал Илюша. — Мне очень нравится, когда я наконец начинаю разбираться в таких вещах, которые сперва кажутся такими уж хитрыми, что не знаешь, с какой стороны и подойти.
— Хорошо, — покорно отвечал Радикс. — Давай попробуем. Начнем вот с чего: убедимся в том, что с помощью перемещения шашек на пустое место мы всегда можем перепрыгнуть через любые две шашки по линии «змейки». Это совершенно ясно, если они обе стоят по соседству с пустышкой у того края, где «змейка» переходят из строки в строку. Но если они стоят где-нибудь рядом в одной строке, то мы можем поступить так: переместим их на край, не нарушая циклического расположения трех шашек (третья — та, которую надо перевести), так, чтобы они стали на краю друг под другом; затем, освободив место для переводимой шашки, перемещаем ее через них и вернемся, не нарушая
— 107 —
циклического расположения трех шашек, к исходному порядку, но с перемещенной уже шашкой. Приведем пример, и все станет ясно (верхний рисунок, стр. 107). Шашку «восемь» переведем через «девять» и «десять». Сперва мы передвинем шашки в двух нижних строках (нижний рисунок на стр. 107). Затем, как показывают три рисунка рядом{9}, мы постепенно передвигаем шашки, потом перескакиваем и возвращаемся обратно. Как видишь, все осталось на месте, только шашка «восемь» перепрыгнула через двух своих соседок.
А теперь нам осталось доказать еще, что все шашки можно поставить на место такими скачками при любом исходном положении, содержащем четное число инверсий. Для этого давай поставим сначала шашку «единица» на первое место, если она еще на нем не стоит. Ясно, что, перескакивая через две шашки, мы ее доведем либо до второго, либо до первого места. Но если «единица» попадет не на первое, а на второе место, мы заставим шашку, которая стоит на первом месте, перепрыгнуть через две шашки направо. Тогда шашка «единица» очутится на первом месте.
