Пятьсот двадцать головоломок

404. Преобразуйте карту следующим образом. Сведите острова A, B, C и D просто к точкам, а мосты превратите в линии, как это сделано в случае 1. Условия задачи от этого не меняются. Если вы соедините A и B, а также C и D линиями, которые будут проходить вне четырехугольника ABCD, то получите случай 2; если же вы подобным образом соедините A и D, а также B и C, то получите случай 3; если же вы соедините A с C, а B с D, то получите случай 4. В каждом из этих случаев B и D представляют собой «нечетные узлы» (точки, из которых можно выйти по нечетному числу путей, а именно по трем путям), так что при любом маршруте вы должны начинать и заканчивать свой путь в В или D для того, чтобы пройти один и только один раз вдоль каждой линии. Следовательно, Томпкинс обязан жить в B или D. Для определенности мы положим, что он живет в B, и поместим Джонсона в D. Всего существует 44 маршрута в случае 2, 44 в случае 3 и 44 в случае 4, что составляет всего 132 маршрута, если мы не различаем маршруты с противоположным направлением обхода. Возьмем, например, случай 2 и обозначим внешние кривые линии через O. Тогда, если вы начнете движение по BOAB, BOAC, BAOB или BAC, каждый из этих вариантов даст по 6 различных маршрутов. Если вы начнете движение по BOAD, BAD, BCOD, BCA или BCD, то получите по 4 маршрута. В случае 3 BOCA, BOCB, BCA или BCOB дадут по 6 маршрутов, a BOCD, BAOD, BAC, BAD или BCD — по 4 маршрута каждый. Аналогичным образом обстоит дело и в случае 4.

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

[Доказано, что можно соединить все точки, расположенные в виде квадрата n×n, непрерывным путем, состоящим из 2n- 2 отрезков прямой, для всех n > 2. Случай n = 3 представляет собой хорошо известную головоломку, которую большинству решить не удается, поскольку те, кто решает, не всегда догадываются продолжить отрезки за пределы квадрата. 5 × 5 — это наименьший квадрат, в котором линия из 2n - 2 отрезков может не выходить за его пределы.

Можно построить замкнутый путь (у такого пути концы совпадают, как в приведенной выше головоломке) из 2n - 2 отрезков для всех квадратов со стороной, большей 3. Квадрат 7 × 7 представляет собой наименьший квадрат с нечетной стороной, для которого существует замкнутый путь из 2n - 2 отрезков, не выходящий за пределы данного квадрата. (Наименьший квадрат с четной стороной, для которого можно нарисовать подобный путь, равен 6 × 6.)

Приведенное здесь Дьюдени решение имеется в книге Сэма Лойда «Cyclopedia of Puzzles» как решение одной из его головоломок. Лойд говорит, что он впервые опубликовал эту головоломку в 1908 г., и отзывается о данном решении как об «удивительно трудном трюке». Позаимствовал ли Лойд свою головоломку у Дьюдени или наоборот, еще не установлено.

Обратите внимание на то, что это решение для случая 7 × 7 является одновременно решением задачи о замкнутом «пути ферзя» на шахматной доске 7 × 7 за 2n- 2 ходов. Замкнутый путь ферзя за 2n- 2 ходов возможен также на любой доске со сторонами, большими 7. Замкнутый путь ферзя за 14 ходов на обычной доске 8 × 8 был впервые найден Сэмом Лойдом, который считал эту задачу одной из лучших своих головоломок.

Число 2n - 2 является необходимым также для любой квадратной доски. — М. Г.]

406. Из дома H до любой из точек, расположенных к северу или к востоку от него, можно добраться лишь одним путем. Поэтому я в этих точках поставил цифру 1. Теперь возьмем второй столбец и заметим, что существуют 3 пути, ведущие во вторую снизу точку, 5 — в следующую, 7 — в следующую за ней и т. д., причем при переходе в очередную расположенную выше точку число путей увеличивается на 2. То же самое применимо и ко второй снизу строке. Выпишем везде соответствующие цифры. Далее, до центральной точки можно добраться 13 путями, поскольку мы можем к ней подойти или из точки снизу (5 путей), или из точки слева (5 путей), или из точки слева внизу по диагонали (3 пути), что в сумме и даст 13 путей. Таким образом, все, что нам осталось сделать,- это выписывать по очереди в каждой точке сумму трех чисел, расположенных в ближайших точках, из которых можно непосредственно попасть в данную. Отсюда мы и получим, что общее число путей, ведущих из H в C, равно 321.

407. На рисунке показано, как лучше всего разрезать сеть. Нетрудно видеть, что 8 разрезов от A до B делят сеть на 2 части.

408. Можно заметить, что каждый участок соединен с остальными четным числом мостов (2, 4 или 6); исключение составляют участки C и L, в которые ведут по 3 моста (нечетное число). Следовательно, чтобы пройти по каждому мосту один и только один раз, необходимо начинать и заканчивать маршрут в C и L, где как раз и расположены дома наших двух приятелей. Так, отправляясь из C, мы можем двигаться по следующему маршруту: C, G, F, C, B, A, D, H, E, I, H, J, K, L, M, G, I, F, B, E, F, I, L.