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

Бобров Сергей Павлович

Конечно, как это в каждом случае сделать - уж вопрос другой (АЛ-1, VIII).

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

– Ишь какой хитрец!
– воскликнул, рассмеявшись, Радикс.
– Причина-то как раз в том и заключается, что ты перескакиваешь через четное число шашек, а ведь всякое четное число состоит из двоек. А если взять две шашки, то уже мы с тобой установили... Впрочем, можно этого отдельно и не рассматривать. Будем рассуждать так. Пусть шашка перепрыгивает по "змейке" через четное число 2n шашек. Причем есть р шашек, с которыми у нее были инверсии, и q = 2n - р шашек,

с которыми инверсий не было. Ясно, что 2n - четное число. Но если это так, то числа р и q, как говорится, одной четности, то есть либо они оба четные, либо оба нечетные, иначе их сумма не могла бы быть четной. Если же я теперь вычту эти два числа одной четности, р и q, друг из друга, то я обязательно получу четное число, так как разность двух четных, как и двух нечетных, чисел неизбежно четная. Можешь проверить, коли тебе не лень. Другими словами, разность двух чисел всегда одинаковой четности с их суммой.

– 106 -

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

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

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

– Ну!
– произнес огорченно Илюша.
– Это мне не очень нравится. Ведь выходит, что мы только полдела сделали.

И, наверно, это самое интересное и есть, потому что мы не получили правила, как приводить шашки в порядок.

– Конечно. Хотя одно общее доказательство вовсе и не должно указывать, как добиться цели скорей всего. Но только дело в том, что это доказательство не простое, и я не уверен, захочешь ли ты его слушать.

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

– 107 -

– Хорошо, - покорно отвечал Радикс.
– Давай попробуем. Начнем вот с чего: убедимся в том, что с помощью перемещения шашек на пустое место мы всегда можем перепрыгнуть через любые две шашки по линии "змейки". Это совершенно ясно, если они обе стоят по соседству с пустышкой у того края, где "змейка" переходят из строки в строку. Но если они стоят где-нибудь рядом в одной строке, то мы можем поступить так: переместим их на край, не нарушая циклического расположения трех шашек (третья - та, которую надо перевести), так, чтобы они стали на краю друг под другом; затем, освободив место для переводимой шашки, перемещаем ее через них и вернемся, не нарушая циклического расположения трех шашек, к исходному порядку, но с перемещенной уже шашкой. Приведем пример, и все станет ясно (верхний рисунок, стр. 107). Шашку "восемь" переведем через "девять" и "десять". Сперва мы передвинем шашки в двух нижних строках (нижний рисунок на стр. 107). Затем, как показывают три рисунка рядом, мы постепенно передвигаем шашки, потом перескакиваем и возвращаемся обратно. Как видишь, все осталось на месте, только шашка "восемь" перепрыгнула через двух своих соседок.

А теперь нам осталось доказать еще, что все шашки можно поставить на место такими скачками при любом исходном положении, содержащем четное число инверсий. Для этого давай поставим сначала

шашку "единица" на первое место, если она еще на нем не стоит. Ясно, что, перескакивая через две шашки, мы ее доведем либо до второго, либо до первого места. Но если "единица" попадет не на первое, а на второе место, мы заставим шашку, которая стоит на первом месте, перепрыгнуть через две шашки направо. Тогда шашка "единица" очутится на первом месте.

Восьмерка перепрыгивает через две шашки ("2" и "11")

Поступим затем тем же порядком и с шашкой "двойка", то есть поместим ее на второе место, и так далее.

Но когда мы дойдем до предпоследнего места, то поставить на него шашку, которая стоит на последнем месте, не удастся, потому что ей ведь для этого надо перепрыгнуть через одну, а не через две шашки. В таком случае в самом конце "змейки", в четвертой строке, мы получим расположение 13-15-14 вместо 13-14-15, и если все остальные шашки уже стоят по местам, то получается только одна инверсия, между "четырнадцатью" и "пятнадцатью". Однако это может случиться только в тех расположениях, где уже с самого начала было нечетное количество инверсий.

– 108 -

Следовательно, при четном числе инверсий все шашки в конце концов неизбежно станут на свои места.

Восьмерка перепрыгивает через четыре шашки ("14", "15", "11" и "2")

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

Илюша поставил (см. рис. на стр. 110).

– Погляди, как в зеркале отражается, и запиши.

Илюша глянул в зеркало и написал то, что видно на рисунке на следующей странице внизу.

– В первой строке "четыре" дает инверсии с "тройкой","двойкой" и "единицей", "тройка" - с "двойкой" и "единицей", наконец, "двойка" - с "единицей".

Всего в первой строке одна плюс две плюс три - шесть инверсий. Во второй строке столько же. В третьей тоже столько же. Всего восемнадцать. А в последней строке только три инверсии. В конечном счете получается двадцать одна инверсия.

– То есть в итоге нечетное число. Значит, если зеркальное расположение "не выходит", его можно перевести в натуральное расположение с одной инверсией. Но раз так, значит, и расположение с одной инверсией можно перевести в зеркальное. А поэтому всякое расположение, которое "не выходит" (и которое, как мы доказали, можно свести к одной инверсии), ты можешь перевести в зеркальное. Так вот, когда у тебя "не выйдет" (возьми-ка поставь в большом Дразнилке пример с перестановкой только двух шашек - "единицы" и "пятнадцати"), то ты можешь для утешения стремиться не к натуральной расстановке шашек, а к зеркальной.

– Вот это так!
– вскричал Илюша. – Беспроигрышный Дразнилка! Здорово! Знаешь, это мне напоминает то странное слово, которое язык тетушки написал в Схолии Четвертой.

– 109 -

Илюша попробовал прием и убедился в его доброкачественности.

– Мне потому нравится Дразнилка, - заявил Илюша, - что все у него выходит просто. Только торопиться не надо!

Радикс усмехнулся.

– Как сказать!
– проворчал он.
– Как сказать! Если ты уж так хорошо все понял, то возьми-ка переверни шашки. На них ведь сзади, как ты помнишь, написано "Тетушка Дразнилка".