Генри Дьюдени - 200 знаменитых головоломок мира

• Название: 200 знаменитых головоломок мира
• Автор: Генри Дьюдени
• Издательство: ООО "Фирма "Издательство ACT"
• Жанр: Математика
• Год: 1999
• ISBN: 5-237-02035-6

Сборник, принадлежащий перу одного из основоположников занимательной математики Генри Э. Дьюдени, содержит увлекательные задачи на темы «Кентерберийских рассказов» Д. Чосера, а также всевозможные логические, арифметические, геометрические и алгебраические головоломки.

Книга несомненно доставит большое удовольствие всем любителям этого жанра.

---

Я показал на рисунке, как можно расположить на шахматной доске 12 коней (наименьшее возможное число), чтобы при этом каждая клетка оказалась либо занятой, либо под угрозой нападения коня. Переберите по очереди все клетки, и вы обнаружите, что дело обстоит именно таким образом. Определите теперь наименьшее число коней, которое требуется, чтобы каждая клетка оказалась либо занятой, либо под ударом, а каждый конь был защищен другим конем. Как следует расставить этих коней? Можно заметить, что из 12 изображенных на рисунке коней лишь 4 защищены подобным образом.

Охраняемая шахматная доска

На обычной шахматной доске 8×8 каждую клетку можно сделать защищенной (то есть либо занятой, либо атакованной) с помощью пяти ферзей — наименьшего возможного количества. Существует ровно 91 фундаментально различное расположение, при котором ни один ферзь не атакует другого ферзя. Если каждый ферзь должен атаковать другого ферзя (или быть им защищенным), то существует по меньшей мере 41 расположение, и я нашел 150 способов, при которых некоторые ферзи атакованы, а некоторые нет, но в последнем случае очень трудно точно перечислить все решения.

На обычной шахматной доске каждую клетку можно защитить восемью ладьями (наименьшее число) 40 320 способами, если ни одна ладья не имеет права атаковать другую ладью, но не известно, сколько среди них существенно различных способов (см. выше решение задачи «Восемь ладей»). Я не пересчитал способы, при которых каждая ладья защищена другой ладьей.

На обычной шахматной доске каждую клетку можно защитить восемью слонами (наименьшее число), если ни одному слону не разрешается атаковать другого слона. Если каждый слон должен оказаться защищенным, то необходимо 10 слонов (см. выше головоломки «Незащищенные слоны» и «Защищенные слоны»).

На обычной шахматной доске каждую клетку можно защитить двенадцатью конями, если все кони, кроме четырех, не защищены. Но если каждый конь должен оказаться защищенным, то требуется 14 коней (см. выше головоломку «Защита коней»).

Если иметь дело с ферзями на досках n×n, где n меньше 8, то представляют интерес следующие результаты:

1 ферзь защищает доску 2×2 одним существенным способом;

1 ферзь защищает доску 3×3 одним существенным способом;

2 ферзя защищают доску 4×4 тремя существенными способами (защищая друг друга);

3 ферзя защищают доску 4×4 двумя существенными способами (не защищая друг друга);

3 ферзя защищают доску 5×5 тридцатью семью существенными способами (защищая друг друга);

3 ферзя защищают доску 5×5 двумя существенными способами (не защищая друг друга);

3 ферзя защищают доску 6×6 одним существенным способом (защищая друг друга);

4 ферзя защищают доску 6×6 семнадцатью существенными способами (не защищая друг друга);

4 ферзя защищают доску 7×7 пятью существенными способами (защищая друг друга);

4 ферзя защищают доску 7×7 одним существенным способом (не защищая друг друга).

Расположения на шахматной доске, не находящиеся под угрозой нападения

Мы знаем, что и ферзей можно всегда разместить на квадратной доске с n2 клетками (если n > 3), чтобы ни один ферзь при этом не атаковал другого ферзя. Однако общей формулы, позволяющей найти число всех таких размещений, еще не найдено; вероятно, ее просто не существует. Известны следующие результаты:

при n = 4 существует 1 фундаментальное решения, а всего 10 решений;

при n = 5 существует 2 фундаментальных решения, а всего 10 решений;

при n = 6 существует 1 фундаментальное решение, а всего 4 решения;

при n = 7 существует 6 фундаментальных решений, а всего 40 решений;

при n = 8 существует 12 фундаментальных решений, а всего 92 решения;

при n = 9 существует 46 фундаментальных решений;

при n = 10 существует 92 фундаментальных решения;

при n = 11 существует 341 фундаментальное решение.

Очевидно, n ладей можно разместить на доске n×n так, чтобы они не атаковали друг друга, n! способами, но вот сколько среди них существенно различных, мне удалось узнать лишь для четырех случаев, когда n равно 2, 3, 4 и 5. Ответами будут соответственно 1, 2, 7 и 23 (см. головоломку «Четыре льва»).

Мы можем разместить 2n—2 слонов на доске n×n двумя способами (см. головоломку «Собрание слонов»). Для досок со стороной в 2, 3, 4, 5, 6, 7 и 8 клеток существует соответственно 1, 2, 3, 6, 10, 20, 36 фундаментально различных размещений. В случае нечетного n существует 21/2(n-1) таких размещений, каждое из которых порождает с помощью поворотов и отражений по 4 других размещения, и 2n-3-21/2(n-3) размещение, порождающие по 8 других размещений. В случае четного n их существует 21/2(n-2), каждое с помощью поворотов и отражений порождает по 4, и 2n-3—21/2(n-4), порождающих по 8 размещений.

На доске и х и мы можем разместить ½ (n2 + 1) коней, не атакующих друг друга, в случае нечетного п одним существенным способом, а когда и четно, то ½n2 коней удается разместить также одним существенным способом. В первом случае мы всех коней размещаем на клетках того же цвета, что и центральная, а во втором случае мы их всех ставим только на черные или только на белые клетки.

Задачи с двумя фигурами

На доске с n2 клетками два ферзя, две ладьи, два слона или два коня всегда можно расположить (безотносительно к тому, атакуют ли они друг друга или нет) способами. Следующие формулы показывают, сколькими из способов две фигуры можно расположить при условии взаимной атаки и без нее.

(См. головоломку «Охота на льва».)

Динамические шахматные задачи

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

148. Путешествие ладьи. В названии этой головоломки я не случайно употребил слово «путешествие», поскольку слово «турне» означает возвращение в исходное место, а в данном случае мы не будем этого делать. Ладья делает 21 ход, посетив каждую клетку доски ровно по одному разу, останавливается в клетке 10 в конце десятого хода и заканчивает путешествие в клетке 21. Два последовательных хода нельзя делать в одном и том же направлении; другими словами, вы должны поворачивать после каждого хода.

149. Еще одна томящаяся дева. Злой барон в добрые старые времена заточил одну невинную деву в глубокую темницу, которая находилась подо рвом замка. На рисунке вы видите 63 камеры темницы, которые соединены между собой открытыми дверьми, и камеру, где прикована дева. Некий доблестный рыцарь, который любил эту деву, сумел вызволить ее из рук врага. Добравшись до входа в темницу, как показано на рисунке, он затем дошел и до камеры, где томилась дева, посетив по дороге каждую камеру ровно по одному разу. Возьмите карандаш и попытайтесь обозначить его путь. Преуспев в этом, попробуйте свести этот путь к 22 прямолинейным отрезкам. Это можно сделать, по-прежнему не посетив ни одну камеру дважды.

150. Подземелье. Случилось когда-то во Франции, что один узник за собственные ли грехи или грехи чужие был брошен в подземелье, где насчитывалось 64 камеры, связанные между собой открытыми дверьми, как показано на рисунке. Дабы чем-то скрасить однообразие заточения, он придумывал себе разные головоломки. Вот одна из них.

Как, начиная с указанной на рисунке камеры, он мог бы посетить каждую камеру ровно по одному разу, сделав при этом как можно больше поворотов? Первая попытка узника отмечена на рисунке пунктиром. Можно заметить, что путь узника состоит из 55 прямолинейных участков, но после многих попыток ему удалось улучшить этот результат. Можете ли вы получить, большее число отрезков? Заканчивать путь разрешается в любой камере. Попробуйте решить головоломку с карандашом в руках на шахматной доске. При желании вы можете рассматривать прямолинейные участки как ходы ладьи.

151. Лев и человек. Некогда на одной из людных площадей Рима находилась тюрьма. Она представляла собой 64 камеры под открытым небом, которые соединялись между собой, как показано на рисунке. За происходившими в ее стенах состязаниями наблюдали с высокой башни. Толпу особенно увлекало зрелище того, как в лабиринте камер искали друг друга (или избегали) христианин и лев. Их помещали в диаметрально противоположные камеры при всех открытых дверях. Как-то человеку дали в руки меч. Он оказался не из трусливых и старался найти льва так же, как лев, несомненно, искал его.