Рис. 31. Как загнать короля в противоположный угол?
Ферзь-богатырь
Если конь — самая хитрая шахматная фигура, а ладья отличается своей прямолинейностью, то ферзь — сильнейшая из фигур, богатырь на шахматной доске. Возможности ферзя чрезвычайно велики, и ему принадлежат многие шахматно-математические рекорды.
Рис. 31. Как загнать короля в противоположный угол?
Может ли один белый ферзь (рис. 31) загнать черного короля из левого нижнего угла в правый верхний, т.е. на поле d3?
Покажем сначала, как загнать черного короля в ближайший угол доски: 1. Фd2 Крb1 2. Фc3 Крa2 3. Фc1 Крb3 4. Фd2 Крa3, и цель достигнута. Труднее перегнать короля в противоположный угол доски.
1. Фc3+ Крa2 2. Фc1 Крb3 3. Фa1 Крc2 4. Фa2+ Крc3 (4...Крc1 “проигрывает” быстрее: 5. Фb3 Крd2 6. Фb1 Крc3 7. Фa2 Крd3) 5. Фb1 Крd2 6. Фb2+ Крd1.
Возникла позиция, центрально-симметричная исходной, но теперь короля нужно загнать в ближайший угол доски. Это мы уже умеем делать. 7. Фa2! Крc1 8. Фb3 Крd2 9. Фb1 Крc3 10. Фa2 Крd3. Предполагалось, что белые сохраняют своего ферзя, иначе решение на ход короче: 6. Фd3+! Крc1 7. Фb3 Крd2 8. Фb1 Крc3 9. Фa2 Крd3.
Аналогичным образом короля можно загнать в любой угол доски mґn, но при условии, что m № n. Но, что удивительно, на квадратных досках завлечь короля на угловые поля, ближайшие к исходному, невозможно. Король блуждает между двумя противоположными углами доски, и ферзь не может изменить его траекторию.
Следующая головоломка того же типа ближе к реальным шахматам.
Задача о неприкосновенном короле. Белый король находится на поле c3 и не имеет права двигаться (почему и называется неприкосновенным). Может ли белый ферзь с помощью своего неприкосновенного короля заматовать одинокого короля черных?
Эта задача была известна еще в прошлом веке. Многие шахматисты, в том числе гроссмейстеры, ошибочно полагали, что заматовать короля нельзя. На помощь была привлечена ЭВМ. Математики А. Брудно и И. Ландау выяснили с помощью машины, что мат всегда дается, причем не позднее двадцать третьего хода (при любом начальном положении белого ферзя и черного короля), но только при неприкосновенном короле на полях c3, c6, f3, f6.
Первый этап решения состоит в том, чтобы загнать черного короля на угловое поле a8 или h1. С этим заданием ферзь справляется без особого труда (устремиться на угловое поле a1 черному королю мешает неприкосновенный король белых; впрочем, там его тоже ожидала бы гибель). В результате получаем позицию, изображенную на рис. 32.
Рис. 32. Задача о неприкосновенном короле.
Если теперь ход черных, то после 1...Крb8 2. Фc6! белые матуют в 10 ходов: 2...Крa7 3. Фc8! Крb6 4. Фd7! Крc5 (4... Крa5 5. Фb7 и 4... Крa6 5. Фc7 Крb5 6. Фd6 приводит к основному варианту) 5. Фe6 Крb5 6. Фd6 Крa5 7. Фb4+ (7. Фc6 пат) 7... Крa6 8. Фb8 Крa5 9. Фb7 Крa4 10. Фa6ґ.
Если же в данной позиции ход белых, то они должны передать его очередь противнику. Это достигается так называемым методом треугольника. Всего четыре хода: 1. Фd5+ Крa7 (1... Крb8 2. Фc6!) 2. Фb5 Крa8 3. Фa6+ Крb8 4. Фc6! — и цель достигнута.
Следующая оригинальная задача тоже иллюстрирует неограниченные возможности ферзя-богатыря.
На доске nґn находятся два белых ферзя и черный король. За сколько ходов белые могут поставить мат? Тот же вопрос для бесконечной доски.
Оказывается, каковы бы ни были размеры доски (она может быть квадратной, прямоугольной и даже бесконечной), и как бы ни располагались в начальный момент два белых ферзя (король им не нужен) и черный король, мат дается не позднее четвертого хода!
Рис. 33. Мат не позднее четвертого кода.
Первым ходом один из ферзей объявляет шах по вертикали; в ответ на отступление короля на одну из соседних линий вторым ходом другой ферзь (с помощью первого) зажимает короля на двух вертикалях. При этом возникает позиция подобная той, что изображена на рис. 33 (обычная шахматная доска составляет фрагмент доски больших размеров или бесконечной доски). На любое движение короля на третьем ходу следует соответствующий горизонтальный шах и мат следующим ходом, например 2... Крe4 3. Фc4+ Крe5 (e3) 4. Фf4ґ.
Одной из самых знаменитых математических задач на шахматной доске, наряду с задачей о ходе коня, является задача о восьми ферзях. Если задачей о ходе коня занимался великий математик Леонард Эйлер, то задача о восьми ферзях привлекала внимание другого великого математика — Карла Гаусса.
Сколькими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали?
Рис. 34. Задача о восьми ферзях.
Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рис. 34 представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок, в чем, собственно, и состоит задача.
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Н\'аук нашел 60 решений и опубликовал их в газете “Illustrierte Zeitung” от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Н\'аук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес. Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.
Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам1. Например, из расстановки, показанной на рис. 34,а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. 34,в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, — на рис. 34,г. При помощи других поворотов и отражений доски можно получить еще пять решений.
Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nґn (при n > 1) для любой расстановки п мирных ферзей возможны три ситуации: 1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается; 2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки; 3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).
В случае 1) исходное решение называется дважды симметрическим, в случае 2) — симметрическим, а в случае 3) — простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.
Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок. Вот один из таких наборов:
1) см. рис. 34,а;
2) см. рис. 34,б;
3) a4, b1, c5, d8, e6, f3, g7, h2;
4) a4, b2, c5, d8, e6, f1, g3, h7;
5) a4, b2, c7, d3, e6, f8, g1, h5;
6) a4, b2, c7, d3, e6, f8, g5, h1;
7) a3, b5, c2, d8, e6, f4, g7, h1;
8) a4, b1, c5, d8, e2, f7, g3, h6;
9) a4, b7, c3, d8, e2, f5, g1, h6;
10) a6, b4, c2, d8, e5, f7, g1, h3;
11) a4, b8, c1, d5, e7, f2, g6, h3;
12) a4, b2, c7, d5, e1, f8, g6, h3.
Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. 34,б является симметрической, другие одиннадцать основных расстановок — простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.
Отметим несколько интересных свойств расстановок мирных ферзей. Симметрическая расстановка на рис. 34,б как ей и положено, обладает внешней симметрией. Она характеризуется также тем, что центральная часть доски (квадрат 4ґ4) не занята ферзями. Свободны здесь и обе главные диагонали доски (этим свойством обладает и восьмая основная расстановка). В первой расстановке (рис. 34,а) никакие три ферзя не находятся на одной прямой, проведенной через центры полей (имеются в виду не только вертикали, горизонтали и диагонали доски, но и прямые с другими углами наклона).
Всякое решение задачи о восьми ферзях можно записать как набор (t1, t2, ј, t8), представляющий собой перестановку чисел 1, 2, ј, 8. Здесь ti — номер горизонтали, на которой стоит ферзь i-й вертикали. Так как ферзи не стоят на одной горизонтали, то все числа ti различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i < j Ј 8) имеем: |tj-ti| № j-i.
Запишем числа 1, 2, ј, 8 сначала по возрастанию, а затем по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки восьми чисел, например такой — (3, 7, 2, 8, 5, 1, 4, 6):
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Полученные суммы образуют два набора: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Рассмотрим следующую задачу.
Какие перестановки чисел от 1 до 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все элементы различны?
Задача о восьми ферзях привлекла внимание Гаусса именно в связи с этой чисто арифметической задачей. Оказывается, между решениями этих двух задач существует взаимно однозначное соответствие. Другими словами, каждая расстановка восьми ферзей, не угрожающих друг другу, дает решение арифметической задачи, и наоборот. Для выбранной перестановки оба набора состоят из различных чисел, и это не случайно — она соответствует первой основной расстановке (см. рис. 34,а).
Нетрудно видеть, что при поворотах и отражениях доски одни решения получаются из других при помощи простых арифметических операций над координатами полей, занятых ферзями. Анализ этих операций позволяет обнаружить дополнительные свойства решений, которые мы не станем обсуждать.
Задача об n ферзях. На шахматной доске nґn расставить n ферзей так, чтобы они не угрожали друг другу.
На доске 1ґ1 один ферзь ставится на одно-единственное поле, и решение существует. На доске 2ґ2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзя поставить некуда. На доске 3ґ3 умещаются только два мирных ферзя. Итак, для досок 2ґ2 и 3ґ3 задача не имеет решения. Эти два случая представляют собой исключение. Для всех n > 3 на доске nґn можно расставить n не угрожающих друг другу ферзей.
На доске 4ґ4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5ґ5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5ґ5.
Заметим, что в общем случае n расстановок (решений задачи) могут заполнить при наложении всю доску nґn только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.
Обобщая алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка n ферзей (t1, t2, ј, tn) на доске nґn является искомой, если для любых i, j (i < j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об п ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах. Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге "Математика на шахматной доске".
На доске nґn (n > 1) расставить 2n ферзей так, чтобы на каждой вертикали, горизонтали и диагонали стояло не более двух из них.
Рис. 35. Задача о 2n ферзях.
На рис. 35,а показана расстановка 16 ферзей на доске 8ґ8, а на рис. 35,б — 18 ферзей на доске 9ґ9; обе они удовлетворяют условию задачи. Первое решение легко обобщается для всех четных досок, а второе для всех нечетных. На четных досках ферзи располагаются парами, а на нечетных одна пара (на средней вертикали) разбивается.
Можно ли расставить на доске 16 ферзей так, чтобы никакие три из них не стояли на одной линии?
Рис. 36. Задача о 16 ферзях.
В отличие от предыдущей задачи, здесь речь идет не только об обычных линиях доски, но и о любых прямых, проходящих через центры полей. Восемь мирных ферзей мы уже расставляли подобным образом (см. рис. 34,а). Оказывается, можно расставить и вдвое больше — 16 ферзей (которые, конечно, уже не являются мирными). Одно из решений задачи показано на рис. 36. Оно является единственным (с точностью до отражений доски), в котором два ферзя занимают центральные поля.
Какое наименьшее число ферзей можно поставить на доске nґn так, чтобы на каждой прямой, проходящей через центр произвольного поля параллельно сторонам или диагоналям доски, стоял хотя бы один ферзь?
Рис. 37. Ферзь на каждой линии доски.
Достаточно поставить 2n ферзей при четных n (т.е. 16 на обычной доске), и 2n+1 ферзей при нечетных n. Способы расстановки ферзей в зависимости от четности n вытекают из рис. 37, где представлены случаи n=8 (рис. 37,а) и n=9 (рис. 37,б). Нетрудно убедиться, что условия задачи выполнены, и меньшим числом ферзей не обойтись.
Задача о ферзях-часовых. Около каждой тюремной камеры можно поставить часового. Находясь у одной из камер, часовой видит, что происходит в некоторых других, от которых к данной ведут коридоры. Каково наименьшее число часовых, необходимое для наблюдения за всеми камерами?
Если шахматную доску рассматривать как тюрьму (да простят нам шахматисты такую аналогию), причем ее поля считать камерами, а вертикали, горизонтали и диагонали — коридорами, то “часовыми” естественнее всего назначить ферзей, которые могут вести наблюдение в любых направлениях. При этом задача о часовых приобретает следующую шахматную формулировку.
Какое наименьшее число ферзей можно расставить на доске так, чтобы они держали под обстрелом все ее свободные поля?
Рис. 38. Задача о ферзях-часовых.
Оказывается, пять ферзей вполне способны справиться со всей шахматной “тюрьмой” (рис. 38). Доказано, что всего существует 4860 расстановок этих пяти ферзей-часовых. В расстановке, изображенной на рис. 38,а, ферзи держат под обстрелом все свободные поля доски, но сами не yrpожают друг другу. На рис. 38,б ферзи стоят на одной диагонали и, значит, обстреливают не только свободные поля доски, но и занятые.
С увеличением размеров доски необходимое число ферзей-часовых, естественно, возрастает. Любопытно, однако, что пяти ферзей хватает и для обстрела cвoбoдных полей досок 9ґ9, 10ґ10 и даже 11ґ11. На рис. 39 расположение ферзей дано сразу для трех этих досок. Внутренний квадрат — это доска 9ґ9; квадрат, который получается при отбрасывании верхней горизонтали и правой вертикали, — доска 10ґ10; наконец, внешний квадрат — доска 11ґ11.
Рис. 39. Пять ферзей-часовых на трех досках.
В общем случае задача о ферзях-часовых является очень сложной, и точная формула для доски nґn неизвестна. Приведем полученные недавно оценки для минимального числа P(n) ферзей-часовых, охраняющих все свободные поля доски nґn:
|
Итак, для охраны обычной доски требуется пять ферзей-часовых. Как бы мы ни расставляли четыре ферзя, по меньшей мере два поля доски останутся без присмотра. В следующей старинной задаче о ферзях требуется, наоборот, оставить неатакованными побольше полей.
Расставить на доске восемь ферзей так, чтобы наибольшее число ее полей оказалось вне поля зрения ферзей.
Рис. 40. На доске 11 безопасных полей.
Максимальное число равно 11, причем при помощи ЭВМ удалось установить, что всего существует семь основных решений (не совпадающих при поворотах и отражениях доски), наиболее симметричное из них приведено на рис. 40 (не атакованные поля отмечены точками).
Обобщение этой задачи заключается в определении максимального числа не атакованных полей на доске nґn при расстановке на ней n ферзей. При n Ј 3, очевидно, таких полей нет. Решение задачи известно только для n Ј 12.
Расставить на доске как можно больше ферзей-часовых так, чтобы при снятии любого из них появлялось ровно одно не атакованное поле.
Рис. 41. Рекорд с одиннадцатью ферзями.
Эту задачу связывает с предыдущей только общий ответ. Указанным образом можно расставить 11 ферзей (рис. 41).
Остановимся теперь на нескольких задачах о путешествиях ферзя-богатыря по шахматной доске.
Какой геометрически самый длинный путь, график которого несамопересекается, может проделать ферзь за пять ходов, начиная с поля d1?
Рис. 42. Длиннейший путь ферзя за пять ходов.
Искомый путь показан на рис. 42. Чаще предлагается другой путь: Фd1-h1-h8-a1-a8-g8. Число полей в данном случае действительно больше (32 > 30), однако в геометрическом смысле этот путь короче. Если ширину одного поля доски считать равной 1, то первый путь длиннее второго лишь на сотые доли, но все-таки длиннее:
|
|
|
За какое наименьшее число ходов ферзь может обойти все поля доски?
Конечно, ферзь может воспользоваться одним из маршрутов ладьи и потратить на обход столько же ходов (15 на открытый маршрут и 16 на замкнутый). Однако он не обязан перемещаться столь прямолинейно и может закончить путешествие на ход раньше (рис. 43,а).
Рис. 43. Маршруты ферзя по доске.
Заметим, что любой кратчайший маршрут ферзя самопересекается (мимо некоторых полей ферзю приходится проходить дважды). Несамопересекающийся маршрут состоит из пятнадцати ходов. На рис. 43, б приведен один из таких маршрутов (он является открытым), его график отличается симметрией.
В занимательной математике известна задача, в которой требуется перечеркнуть четырьмя линиями девять точек, расположенных в форме квадрата, не отрывая карандаша от бумаги. Эту задачу можно сформулировать в шахматных терминах.
Может ли ферзь за четыре хода обойти все поля доски 3ґ3?
Рис. 44. Как обойти доску 3ґ3 за четыре хода.
Будем считать (и это очень важно), что наша маленькая доска является фрагментом обычной шахматной доски (занимает ее левый нижний угол). Искомый маневр ферзя изображен на рис. 44. В задаче имеется небольшая ловушка — для достижения цели ферзю приходится дважды покинуть доску 3ґ3.
Закончим эту главу одним интересным обобщением задачи о восьми ферзях, придуманным сравнительно недавно.
Расставить на доске максимальное число ферзей так, чтобы каждый из них нападал ровно на p ферзей.
Рис. 45. Обобщение задачи о восьми ферзях.
Условие p=0 означает, что ферзи не должны нападать друг на друга, и мы приходим к классической задаче; искомое число ферзей равно восьми. Доказано, что при p=1 (под боем у каждого ферзя находится один ферзь) максимум равен десяти (рис. 45,а), а при p=2 — четырнадцати (рис. 45,б). Для больших значений p задача еще не решена до конца. Для p=3 найдена расстановка шестнадцати ферзей (она очень проста — ферзи размещаются на первой последней горизонталях доски), а для p=4 — двадцати одного ферзя (вся граница доски, кроме полей a1, a8, c8, f8, h8, h6, h5, h4, h1, а также ферзи на полях c6 и g7).
1Предполагается, что при поворотах и отражениях доски система координат фиксирована. В противном случае при любых операциях с доской мы бы имели одно и то же решение.
| Оглавление |