<< Предыдущая

стр. 36
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


точку по соседнему мосту, оставив одну точку x обязательно вовне. В случае 2 имеются 4 нечетных узла A, B, T T T T T T T T T




D и x (если мы решили входыT и выходы сделать такими, как в случае 3); поэтому, как я уже объяснял, нам
T T T T T T T




потребуется 2T росчерка (половина 4), чтобы пройти по всем путям, откуда и следует неразрешимость нашейT
T




задачи.T
T




Теперь давайте удалим отрезок ABT. Тогда A и B станут четными узлами, а нам придется начинать иT
T T T T T T T




заканчивать наш маршрут в нечетных узлах D и x. Двигайтесь вдоль линии, показанной в случае 3, и выT
T T T T T T T




увидите, что это можно сделать, выбросив путь от A до B. Эту схему читатель легко преобразует вT случай 4,
T T T T T T T T




сказав себе: «Идем из x в D, из D в E, из E наружу и возвращаемся в E» и т. д.T Маршрут можно изменить,
T T T T T T T T T T T T T




соединив внешние мосты по-другому: принять за x внешний мост,T идущий в A или B вместо D, и выбросить T T T T T T T T T




любой из путей ABT, ADT, BDT, xAT, xB или xDT. ВT случае 5 путь из x идет в B. Мы по-прежнему выбросили ABT, но
T T T T T T T T T T T T T T T T T T T T T




должны теперь начинать иT заканчивать движение в D и x. Преобразовав эту диаграмму (см. случай 6), можно
T T T T T T T




заметить, чтоT получился тот же самый чертеж, который я приводил, формулируя задачу. Теперь читатель можетT
T




начертить столько маршрутов, сколько пожелает, но при этом всегда придется удалять один изT путей (мостов).
T T




На примере нашей головоломки хорошо видно, как некоторая изобретательностьT (вроде той, что была T




проявлена при преобразовании диаграмм) помогает нащупать правильныйT подход.T T
404. Преобразуйте карту следующим образом. Сведите острова A, B, C и D просто к точкам, а мостыT
T T T T T T T T T




превратите в линии, как это сделано в случае 1. Условия задачи от этого не меняются. Если вы соедините A и B,
T T T T T T T T




а также C и D линиями, которые будут проходить вне четырехугольника ABCDT, то получите случайT 2; если же
T T T T T T T T




вы подобным образом соедините A и D, а также B и C, то получите случай 3; если же выT соедините A с C, а B с
T T T T T T T T T T T T T T T T T




D, то получите случай 4. В каждом из этих случаев B и D представляют собойT «нечетные узлы» (точки, из
T T T T T T T T T




которых можно выйти по нечетному числу путей, а именно по трем путям), такT что при любом маршруте вы T




должны начинать и заканчивать свой путь в В или D для того, чтобыT пройти один и только один раз вдоль T




каждой линии. Следовательно, Томпкинс обязан житьT в B или D. Для определенности мы положим, что он T T T T T




живет в B, и поместим Джонсона в D. Всего существует 44 маршрута в случае 2, 44 в случае 3 и 44 в случае 4,
T T T T T T




что составляет всегоT 132 маршрута, если мы не различаем маршруты с противоположным направлением
T




обхода.T Возьмем, например, случай 2 и обозначим внешние кривые линии через O. Тогда, если вы начнетеT
T T T




движение по BOABT, BOACT, BAOB или BACT, каждый из этих вариантов даст по 6 различныхT маршрутов. Если
T T T T T T T T T T




вы начнете движение по BOADT, BADT, BCODT, BCA или BCDT, то получите по 4T маршрута. В случае 3 BOCAT,
T T T T T T T T T T T T T




BOCBT, BCA или BCOB дадут по 6 маршрутов, a BOCDT, BAODT, BACT, BAD или BCDT — по 4 маршрута
T T T T T T T T T T T T T T T T T




каждый. Аналогичным образом обстоит дело и в случаеT 4. T T T
405. На рисунке показано, каким образом военный корабль может потопить 49 судов за 12 прямыхT курсов,
T T




закончив движение в той же точке, откуда начал. Двигайтесь вдоль каждой прямой до того места,T где он меняет T




направление.T

[Доказано, что можно соединить все точки, расположенные в виде квадрата n n, непрерывным путем,T
T T T T T




состоящим из 2n- 2 отрезков прямой, для всех n > 2. Случай n = 3 представляет собой хорошо известнуюT
T T T T T T T T T T T T




головоломку, которую большинству решить не удается, поскольку те, кто решает, не всегда догадываютсяT
T




продолжить отрезки за пределы квадрата. 5 5 — это наименьший квадрат, в котором линия из 2n - 2 отрезков
T T T T T T T T T T T




может не выходить за его пределы.T

Можно построить замкнутый путь (у такого пути концы совпадают, как в приведенной вышеT головоломке)
T T




из 2n - 2 отрезков для всех квадратов со стороной, большей 3. Квадрат 7 7 представляетT собой наименьший
T T T T T T T T T T




квадрат с нечетной стороной, для которого существует замкнутый путь из 2n - 2 отрезков, не выходящий за T T T T T T




пределы данного квадрата. (Наименьший квадрат с четной стороной, дляT которого можно нарисовать подобный T




путь, равен 6 6.)T T T T T




Приведенное здесь Дьюдени решение имеется в книге Сэма Лойда «Cyclopedia of Puzzles» как решениеT
T




одной из его головоломок. Лойд говорит, что он впервые опубликовал эту головоломку в 1908 г., иT отзывается
T T




о данном решении как об «удивительно трудном трюке». Позаимствовал ли Лойд своюT головоломку у Дьюдени T




или наоборот, еще не установлено.T

Обратите внимание на то, что это решение для случая 7 7 является одновременно решением задачи оT
T T T T T




замкнутом «пути ферзя» на шахматной доске 7 7 за 2n- 2 ходов. Замкнутый путь ферзя за 2n- 2 ходовT
T T T T T T T T T T T T T T T




возможен также на любой доске со сторонами, большими 7. Замкнутый путь ферзя за 14 ходов на обычнойT
T




доске 8 8 был впервые найден Сэмом Лойдом, который считал эту задачу одной из лучших своихT
T T T T T

<< Предыдущая

стр. 36
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>