Сергей Бобров - ВОЛШЕБНЫЙ ДВУРОГ
Илюша нарисовал чертеж и углубился в его рассмотрение.
Двойной лабиринт Радикса.
- 56 -
- Да, - сказал Илюша, - действительно, в центр не попаду. Тогда, мне кажется, можно поступить так. При обходе лабиринта по правилу правой руки я убеждаюсь, что в центр не могу попасть, и замечаю, что какой бы рукой я ни пользовался, всегда на противоположной от меня стене, то есть на той, которой я не касаюсь рукой, мне встречается дверь, и я в нее не попадаю. Если в лабиринте есть такая дверь, то я поставлю против нее крестик на моей стене, сменю руку и пойду кругом островка. Когда я попаду в эту дверь, то дойду до центра, выйду из него и, снова дойдя до моего крестика, сменю руку во второй раз. Мне кажется, что это получается лабиринт в лабиринте, и, по-моему, такой лабиринт надо называть двойным. Так можно и тройной построить!
- Можно, - спокойно ответствовал Радикс. - Во-первых, эта система внутренних петель и островков может быть довольно сложной, а во-вторых, именно на такого рода усложнениях и основана путаница лабиринта. Ну, что у тебя еще есть? Выкладывай. А к лабиринту мы вернемся еще.
- Еще про этого противного Доктора Узлов. Почему он так называется?
- Начнем с его рожицы, - отвечал Радикс. - Ее линии, как ты заметил, легко можно обойти, пройдя при этом один раз по каждой линии. Такая фигура называется уникурсальной. Вот почему его так зовут.
Правда, это слово - "уникурсальный" - иногда применяется и в другом смысле, но уж этого мы касаться не будем. Уникурсальную фигуру можно начертить, не отнимая пера от бумаги, как говорится - одним росчерком. Конечно, так начертить можно не всякую фигуру. Попробуй, например, начертить фигуру, нарисованную налево.
Попробуй начертить одним росчерком!
У тебя ничего не получится, как бы ты ни старался. Эта фигура не уникурсальная.
- 57 -
- В чем же тут дело? - спросил Илюша. - Как узнать, какая фигура уникурсальная, а какая нет?
- Назовем каждый перекресток нашей фигуры узлом. Если от него отходит четное число путей, то это будет четный узел, а если нечетное - нечетный. Если узел четный, то ты можешь прийти к нему и уйти от него по новому пути. Сколько бы ни было четных узлов, они тебе не помешают.
Нечетный узел.
В каждый из них ты можешь пройти.
Другое дело - нечетный узел. Например, из него три пути...
- Ясно, - подхватил Илюша. - Раз приду и раз уйду - значит, две дороги я уже использовал. А опять приду по третьей - и конец, потому что нехоженых дорог больше нет.
- Совершенно верно, - отвечал терпеливый Радикс. - Ну, а что будет, если ты встретишь два нечетных узла?
- Допустим, что они будут тройные.
- Два нечетных узла? .. - повторил Илюша. - Я сейчас нарисую.
Илюша нарисовал два чертежа.
Один изображал два ромба, соединенных прямой, а другой ромб с одной диагональю (рисунок на стр. 59).
- Ну вот, - сказал он, - две фигуры с двумя нечетными, тройными узлами. Попробую начать с первой. Итак, я выхожу из нечетного узла, то есть из точки А, потом возвращаюсь к нему через В, С и D и выхожу из него опять. Значит, я все его пути уже прошел. Иду по последнему пути, то есть через АЕ во второй узел (в точку Е). Прихожу во второй, выхожу из него по второму пути и через F, G и H возвращаюсь в Е обратно по третьему пути. Значит, выходит так: если у меня два нечетных узла, то я могу из одного прийти в другой, но во втором застряну, и дальше мне уже некуда будет идти...
- Так, - сказал Радикс. - Из этого, я думаю, тебе ясно, что больше двух нечетных узлов в уникурсальной фигуре быть не может, а четных может быть сколько хочешь. Ты можешь нарисовать фигуру с двумя нечетными узлами, а между ними наставить сколько угодно четных. И это будет уникурсальная фигура.
- 58 -
Если есть только одни четные узлы, то ты, обойдя фигуру, вернешься к тому узлу, с которого начал, а если в твоей фигуре есть два нечетных узла, то ты уже вернуться к тому узлу, с которого начал, не можешь, а закончишь путешествие в другом. А теперь изобрази-ка мне схему путей на ордене Уникурсала Уникурсалыча и узлов, в которых эти пути сходятся.
- Как это? - спросил Илюша.
- Ты водишь пальцем по дорожкам и мостам, вот и покажи, по каким линиям ты при этом двигаешься. Поэтому давай изобразим условно оба берега и оба острова точками, а мосты - линиями, соединяющими эти точки.
Илюша начертил фигуру, нарисованную внизу.
- Ну вот, - сказал Радикс. - Это и есть схема путей и перекрестков на ордене Уникурсала Уникурсалыча. Ясно, что вопрос о том, можно ли обойти все мосты, проходя через каждый только один раз, сводится к вопросу, можно ли вычертить эту фигуру непрерывным движением, то есть уникурсальна она или нет.
Илюша начал рассматривать схему, раза два сбился и наконец ответил:
- Тут выходит четыре нечетных узла - А, В, С и D.
- Ну, вот тебе и решение! -усмехнулся Радикс. - Мы с тобой сейчас установили, что в уникурсальной фигуре может быть любое число четных узлов и не более двух нечетных. Если в фигуре есть только четные узлы, то обход фигуры можно начать с любой точки.
- 59 -
Если в фигуре есть два нечетных узла, то нужно начать обход именно с одного из них, а закончить в другом нечетном узле. А теперь представь, что тебе дана очень сложная фигура без нечетных узлов или с двумя нечетными узлами.
Какие основания утверждать, что ты, выйдя из первого нечетного узла, сможешь обойти ее всю, не проходя ни одного пути дважды?
- Если она не состоит из нескольких несвязанных частей, то я, конечно, могу попасть в любую точку, а в четных узлах застрять не могу...
- Таким образом, раньше всего надо сказать, что фигура должна быть связной. А не может ли случиться, что ты, проходя через четные узлы, оставишь в стороне какую-нибудь часть фигуры так, что к ней уже больше нельзя будет добраться, а потом застрянешь во втором нечетном узле и не обойдешь всю фигуру?
- Как же это может случиться? - спросил Илюша.
- А вот, например, если на нашем первом чертеже, где два ромба соединены перемычкой, ты сначала пойдешь не по сторонам одного из ромбов, а по этой перемычке. Однако то же самое может случиться и как-нибудь иначе, если ты незаметно для себя разобщишь две части фигуры и она потеряет связность. Это значит, что свободных, то есть еще не пройденных путей, соединяющих две эти части, уже не останется.
Представь себе, что путь, по которому ты только что прошел, тем самым вычеркнут: ведь второй раз по нему идти нельзя, и, следовательно, он для тебя уже больше не существует.
Вот тебе фигура: если ты пойдешь по пути ABCDEA, то вычеркнешь путь BCDE, а ромб CFDG окажется отрезанным.
- Значит, я шел неправильно. Мне надо было прежде из D попасть не в Е, а обойти сперва ромб DFCG, то есть идти в F или G.
- Это, конечно, верно, но только для данного случая. Вот ты говоришь, что шел неправильно. Но для того, чтобы идти правильно, надо показать, что возможно найти правильный способ обхода и при этом не для какой-нибудь определенной фигуры, а в самом общем виде, то есть для любой заданной фигуры, как бы она ни была сложна. Не забудь, что при этом ты должен будешь рассуждать, не зная ничего об этой фигуре, кроме того, что это фигура связная и что в ней нечетных узлов или совсем нет, или только два. Именно так следует поставить задачу общего математического доказательства.
- 60 -
- Я буду рассуждать так. Раз это фигура связная, то, значит, я имею возможность так или иначе из первого узла попасть в тот, где должно закончиться мое путешествие, то есть либо во второй нечетный узел, либо, если это фигура только с одними четными узлами, вернуться обратно в начальный узел. Чтобы не путаться, я самый простой такой маршрут отмечу красной линией, а остальные оставлю черными. А затем пойду по этой красной линии, но в каждом узле буду останавливаться и проверять, нет ли из него еще черных путей, которые надо обойти раньше, чем отправиться дальше по красному маршруту. Вот это и значит "идти правильно".
- Нет, - ответил Радикс, - это еще не всё. Почему ты так уверен, что можешь обойти каждую из твоих черных фигур?
- Потому что все узлы у них четные. И если в точках, через которые проходят и красные пути, не считать этих красных путей, то для черных путей и эти узлы тоже будут четными...
- Справедливо! Но ведь таким образом мы приходим к той же самой задаче: снова надо доказать, что можно обойти эти фигуры. И вот мы подошли к самому важному пункту нашего рассуждения. Теперь будет не так трудно. Потому, что нам удалось привести задачу об обходе фигуры с некоторым данным числом путей к задаче об обходе фигуры с меньшим числом путей. Понимаешь?
- Понимаю! - воскликнул Илюша. - А эти новые, более простые задачи я опять сведу к таким же, но еще более простым... И так можно каждый раз уменьшать число путей, а ведь нам дано только некоторое определенное число путей...
