Генри Дьюдени - Пятьсот двадцать головоломок

• Название: Пятьсот двадцать головоломок
• Автор: Генри Дьюдени
• Издательство: Мир
• Жанр: Математика
• Год: 1975

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

В предлагаемой книге собрано 520 задач и головоломок Дьюдени по арифметике, алгебре, геометрии, разрезанию и составлению фигур. Читателя ждет встреча с постоянно действующими героями Дьюдени — семейством Крэкхэмов, профессором Рэкбрейном и др.

Книга доставит удовольствие всем любителям занимательной математики.

---

Так, мы сначала наполняем 5-литровый кувшин из одного бидона, затем 4-литровый кувшин из 5-литрового, затем выливаем содержимое 4-литрового обратно в бидон и т. д. Все это можно проделать очень легко. Обратите внимание на остроумие последних двух операций: мы наполняем 4-литровый кувшин из второго бидона, а затем доверху доливаем первый бидон.

401. Жирная линия на рисунке показывает путь из Лондона в Типперери, совершаемый за 18 переходов. Чтобы добраться до места назначения за четное число переходов, совершенно необходимо включить в маршрут переход, отмеченный словами Ирландское море.

402. Десять точек, отмеченных на рисунке буквами, представляют собой «нечетные узлы», то есть точки, из которых вы можете идти по нечетному числу (три) направлений. Следовательно, нам известно, что всего потребуется 5 линий (половина 10). Пунктирные линии показывают 4 кратчайших расстояния между узлами. Обратите внимание, что вам нельзя использовать один узел дважды; в противном случае решение можно было бы удушить, обозначив пунктиром EH и CF вместо CD и GH. Зафиксировав наши 4 кратчайших расстояния, мы можем начертить все остальное с помощью одной непрерывной линии от A до K, как показано на рисунке. Добравшись до D, вы должны пройти к C и обратно к D, от G к H и обратно и т. д. Или же вы можете подождать до того момента, когда доберетесь до C, а затем пройти до D и обратно и т. д. Таким образом, вы пройдете дважды только пунктирные линии, что и даст минимально возможное расстояние, которое приходится проходить дважды.

403. Допустим, что мы пересекаем отрезки по мостам, изображенным в случае 1 маленькими параллельными линиями. Далее я преобразую диаграмму, сведя области A, B, C, D, E просто к точкам и изобразив мосты, связывающие данные точки, прямыми, или путями, — случай 2. При этом никакого изменения условий не произошло, поскольку в каждом случае имеется 16 мостов (путей) и они связывают A, B, C, D, E совершенно одинаковым образом. Можно заметить, что наружу выходят 9 мостов, или путей. Очевидно, мы можем попарно соединять данные пути, заботясь лишь о том, чтобы они не пересекали друг друга. Простейший способ показан в случае 3. Выйдя из A, B, C или E, мы немедленно возвращаемся в ту же точку по соседнему мосту, оставив одну точку x обязательно вовне. В случае 2 имеются 4 нечетных узла A, B, D и x (если мы решили входы и выходы сделать такими, как в случае 3); поэтому, как я уже объяснял, нам потребуется 2 росчерка (половина 4), чтобы пройти по всем путям, откуда и следует неразрешимость нашей задачи.

Теперь давайте удалим отрезок AB. Тогда A и B станут четными узлами, а нам придется начинать и заканчивать наш маршрут в нечетных узлах D и x. Двигайтесь вдоль линии, показанной в случае 3, и вы увидите, что это можно сделать, выбросив путь от A до B. Эту схему читатель легко преобразует в случай 4, сказав себе: «Идем из x в D, из D в E, из E наружу и возвращаемся в E» и т. д. Маршрут можно изменить, соединив внешние мосты по-другому: принять за x внешний мост, идущий в A или B вместо D, и выбросить любой из путей AB, AD, BD, xA, xB или xD. В случае 5 путь из x идет в B. Мы по-прежнему выбросили AB, но должны теперь начинать и заканчивать движение в D и x. Преобразовав эту диаграмму (см. случай 6), можно заметить, что получился тот же самый чертеж, который я приводил, формулируя задачу. Теперь читатель может начертить столько маршрутов, сколько пожелает, но при этом всегда придется удалять один из путей (мостов). На примере нашей головоломки хорошо видно, как некоторая изобретательность (вроде той, что была проявлена при преобразовании диаграмм) помогает нащупать правильный подход.

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.