Яков Перельман - Веселые задачи. Две сотни головоломок

Рис. 158. Муха на кристалле.

— И при этом на практике решает интересную задачу: обойти многогранник по его ребрам, не посещая дважды ни одного ребра.

— Разве это возможно?

— В данном случае вполне: ведь этот кристалл — восьмигранник.

— Да, октаэдр. И что же?

— У него на каждой вершине сходятся 4 ребра.

— Разумеется. Но какое отношение это имеет к нашей задаче?

— Самое непосредственное. Задача обойти все ребра многогранника, и притом не более чем по одному разу, разрешима только для тех многогранников, у которых в каждой вершине сходится четное число ребер.

— Вот как! Я об этом не знал. Почему же?

— Почему в каждой вершине должно сходиться именно четное число ребер? Очень просто. Ведь в каждую вершину надо попасть и надо из нее уйти, причем прийти по одной дороге, а уйти по другой, значит, нужно, чтобы в ней сходилась пара ребер. Если же, путешествуя по кристаллу, вы попадете на вершину вторично, если к ней ведет еще и третье ребро, то должно иметься непременно и четвертое, чтобы вы могли уйти с этой вершины, а не очутиться в тупике. Другими словами, число ребер, сходящихся в каждой вершине, должно быть парное, т. е. четное. Если хотя бы одна вершина многогранника имеет нечетное число сходящихся в ней ребер, то на такую вершину вы, конечно, можете, исчерпав все ведущие к ней парные ребра, попасть по последнему неиспользованному ребру, но покинуть эту вершину вам уже не удастся: путешествие здесь поневоле оборвется.

— Но ведь я могу просто не воспользоваться этим ребром, раз оно заведомо ведет в тупик!

— Тогда вы не выполните другого условия нашего путешествия: пройти по всем ребрам без исключения.

— Позвольте, но может же случиться, что это ребро как раз последнее и единственное, еще не пройденное. Тогда нет вовсе надобности покидать его: оно и будет конечной целью путешествия.

— Совершенно правильно. И если бы в фигуре была только одна «нечетная» вершина, то вам нужно было бы избрать такой маршрут, чтобы вершина эта оказалась последним этапом — тогда вы разрешили бы задачу успешно. Или же начать движение с этой вершины — тогда вам не пришлось бы в нее возвращаться. Однако, фигур с одной «нечетной» вершиной не существует: таких вершин должно быть четное число — две, четыре, шесть и т. д.

— Это почему же?

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

— А если соседняя вершина и без этого ребра «нечетная»? Тогда новое ребро делает ее «четной», и наша «нечетная» вершина остается одинокой.

— Этого не может быть. Если без нашего ребра у соседней вершины сходится нечетное число ребер, то, значит, одно из ее непарных ребер соединено с какой-то другой вершиной, и следовательно, «нечетная» вершина еще будет найдена. Иначе говоря, если в фигуре имеется одна «нечетная» вершина, то непременно должна существовать и вторая. Число «нечетных» вершин не может быть нечетным. Поясню это еще и иным путем, пожалуй, более простым. Представьте, что вам нужно сосчитать число ребер в какой-то фигуре. Вы считаете ребра, сходящиеся в одной вершине, прибавляете ребра, сходящиеся во второй, потом — в третьей и т. д. Когда вы все это сложите, что у вас получится?

— Двойное число ребер фигуры, потому что каждое ребро считалось дважды: ведь каждое ребро соединяет две вершины.

— Именно. Вы получите удвоенное число ребер. И если допустить, что в одной из вершин сходится нечетное число ребер, а во всех прочих — четное, то результатом сложения будет, конечно, число нечетное. Но может ли удвоенное целое число быть нечетным?

— Не может, конечно. Теперь мне совершенно ясно, что «нечетных» вершин во всякой фигуре должно быть две, четыре, т. е. обязательно четное число. Все же я думаю, что и кристалл с двумя «нечетными» вершинами возможно обойти. Пусть у нас имеется фигура с двумя «нечетными» вершинами. Что мешает начать путешествие именно в одной из этих точек и закончить в другой? Тогда не понадобится ни возвращаться в первую, ни уходить из последней. Путешествие будет выполнено с соблюдением всех требуемых условий.

— Правильно! В этом и состоит секрет успешного выполнения подобных путешествий, или — что то же самое — правило вычерчивания фигур одним росчерком пера. Если потребуется непрерывным движением начертить фигуру — безразлично, в плоскости или в пространстве, — то прежде всего внимательно ее рассмотрите и определите, имеются ли у этой фигуры «нечетные» вершины, т. е. такие, у которых встречается непарное число линий. Если подобных вершин в фигуре больше двух, то задача неразрешима. Если только две, то нужно начать вычерчивание в одной «нечетной» точке и закончить в другой. Если «нечетных» вершин вовсе нет, то можно начинать чертить из любой вершины, и всегда найдется способ вычертить всю фигуру и вернуться в начальную точку. Каким путем вы в таком случае поведете перо — безразлично. Надо только заботиться о том, чтобы не вести линию к вершине, от которой нет больше пути, т. е. стараться не замыкать фигуру раньше времени. Вот пример: фигура в форме буквы Ф (рис. 159) — Можно ли ее начертить одним росчерком пера?

Рис. 159.

— В ней всего две «нечетные» вершины — концы «палки». Значит, начертить ее одним росчерком пера возможно. Но как?

— Нужно начать с одного конца «палки» и кончить другим (рис. 160).

Рис. 160.

— В детстве я ломал голову над тем, чтобы начертить одним росчерком пера четырехугольник с двумя диагоналями (рис. 161). Мне этого никак не удавалось сделать.

Рис. 161.

— И неудивительно: ведь в этой фигуре 4 «нечетные» вершины — углы четырехугольника. Бесполезно даже ломать голову над этой задачей: она неразрешима. — А что скажете вы о фигуре, изображенной на рис. 162?

Рис. 162.

— Ее тоже нельзя начертить одной непрерывной линией, потому что у нее 4 вершины, в каждой из которых сходится по 5 линий, т. е. у нее 4 «нечетных» вершины. Зато легко начертить фигуры, показанные на рис. 163 и 164: у них все вершины «четные» (решение для второй фигуры см. на рис. 165).