Глава 6. Неповоротливая ладья

Ладья является самой распространенной фигурой в комбинаторных задачах на шахматной доске и часто упоминается даже в серьезной математической литературе. Что общего, скажем, между шахматным термином «ладья» и чисто математическим понятием «многочлен»? Тем не менее американский математик Дж. Риордан23 как раз применяет термин «ладейный многочлен»! Чем это вызвано? Оказывается, большой класс важных комбинаторных задач сводится к подсчету числа тех или иных расстановок ладей на шахматной доске. При рассмотрении ряда сложных задач существенную роль играет многочлен

r₀ + r₁x + r₂x² + … + r_kx^k + … + r_nxⁿ,

где r_k - число размещений k ладей на доске n×n, не угрожающих друг другу (к = 1, …, n). Этот многочлен Риордан и называет ладейным. Как мы видим, такое название вполне оправдано.

Многие задачи из комбинаторики, теории групп и теории чисел удобно интерпретируются в «ладейных» терминах. Приведем один комбинаторный пример24. Пусть n рабочих назначаются на n различных работ, причем каждая из них должна выполняться только одним рабочим.

Спрашивается, сколькими способами можно осуществить такое назначение?

Поставим в соответствие рабочим горизонтали шахматной доски n×n, а работам - ее вертикали. Если i-й рабочий назначается на j-ю работу, то на поле, соответствующее пересечению i-й горизонтали и j-й вертикали, поставим ладью. Так как каждая работа выюлняется одним рабочим и каждый рабочий назначаете! на одну работу, то в результате на любой вертикали и горизонтали будет стоять по одной ладье. Другими словами, никакая пара из этих n ладей не будет угрожать друг другу25. Таким образом, нашей задаче о назначении мэжно придать вполне шахматный характер.

Сколькими различными способами на доске n×n можно расставить n не угрожающих друг другу ладей?

Заметим, что при расстановке более n ладей хотя бы на одной вертикали или горизонтали их окажется не менее двух. Таким образом, n есть наибольшее число ладей на доске n×n, не угрожающих друг другу. Одна из простейших расстановок заключается в расположении ладей вдоль главной диагонали доски (на полях a1, b2, c3, d4, e5, f6, g7, h8 для обычной доски)26.

Выясним теперь, сколько существует указанных расположений n ладей. Назовем ладыо, стоящую на первой вертикали, - первой, стоящую на второй вертикали - второй, и т. д., вплоть до n-й ладьи, стоящей на n-й вертикали. Первую ладью можно поместить на любую из n горизонталей, затем вторую - на любую из (n - 1) оставшихся горизонталей (занятая первой ладьей исключается, так как никакие две ладьи не должны угрожать друг другу), третью ладью - на любую из (n - 2) оставшихся горизонталей и т. д., вплоть до (n - 1)-й ладьи, для которой остается выбор из двух горизонталей, и последней, n-й ладьи, которая ставится на единственную оставшуюся горизонталь. Комбинируя n различных расположений первой ладьи с (n - 1) расположениями второй, (n - 2) - третьей и т. д., получаем n (n - 1) … 2 · 1 = n! различных расположений всех n ладей. Это число и является искомым. В частности, на обыкновенной шахматной доске восемь ладей, не угрожающих друг другу, можно расположить 8! = 40320 различными способами.

Если ладьи занумерованы, то существует уже (n!)² различных расположений n ладей, не угрожающих друг другу. Это следует из того, что n подходящих полей можно выбрать n! способами и столько же способов имеется для расположения на этих полях n занумерованных ладей.

Итак, n рабочих можно назначить на n работ n! способами. Пусть теперь нужно сделать новое назначение, причем каждый рабочий хочет сменить свою предыдущую работу. Сколько существует таких назначений? В «ладейной» постановке эта задача формулируется так:

Сколькими различными способами на доске n×n можно расставить n ладей, не угрожающих друг другу и не стоящих на главной диагонали (для обычной доски - на диагонали a1 - h8)?

Дополнительное условие значительно затрудняет решение задачи. Даже Эйлеру не удалось найти общую формулу для числа А_n указанных расстановок. Правда, он вывел рекуррентное соотношение А_n = (n - 1) (A_n-1 + А_n-2), с помощью которого можно последовательно определить значения А_n для любого n ≥ 3 (А₁ = 0, А₂ = 1). Окунев приводит элементарный вывод формулы для A_n, она имеет следующий вид:

Для n = 8 получаем

т. е. при дополнительном условии число расстановок восьми ладей, не угрожающих друг другу, уменьшается почти втрое.

Какое наибольшее число ладей можно расставить на доске n×n так, чтобы каждая из них была под ударом не более чем одной из остальных?

В отличие от предыдущих задач здесь ладьи могут угрожать друг другу, правда, более одной угрозы не допускается. Покажем, что больше 4n/3 ладей расставить указанным образом невозможно. Пусть к ладей расставлены на доске с соблюдением условия задачи. На всех полях с ладьями напишем число 0, затем с каждой из n вертикалей проделаем следующую операцию: если на ней стоят два числа (имеются в виду только поля с ладьями), то прибавим к обоим по 1; если одно число, то прибавим 2. Теперь точно такую же операцию проделаем со всеми горизонталями. Легко видеть, что в результате на каждом из k полей с ладьями будет написано число 3 или 4 и поэтому сумма s всех написанных чисел не меньше 3k. С другой стороны, поскольку в каждую из n вертикалей и затем в каждую из n горизонталей мы добавили не более чем 2, то s не больше 4n. Итак, 3k ≤ s ≤ 4n, откуда k ≤ 4n/3.

Для n = 8 получаем k ≤ 32/3, т. е. k ≤ 10. Ровно 10 ладей, удовлетворяющих условию задачи, можно расставить так: ладьи a8, b8, c6, c7, d5, e5, f3, f4, g2, h2. Аналогично на доске n×n (при любом n) можно расставить [4n/3] ладей (квадратные скобки означают целую часть числа), что и является ответом на задачу.

Ясно, что ферзей указанным способом можно расставить не больше, чем ладей. На обычной доске 10 ферзей, т. е. максимальное число, расставляются, например, так: ферзи a8, b8, c3, c4, d7, e7, f2, g1, b5, b6. Однако в общем случае задача для ферзей не решена.

Очевидно, восемь ладей, не угрожающих друг другу на доске 8×8, держат под обстрелом все поля доски27. В общем случае наименьшее число ладей, обладающих тем же свойством, равно п. Если ладей меньше, то найдется хотя бы одна вертикаль и горизонталь, на которых нет ладей, и поле, стоящее на их пересечении, не атаковано ладьями. Возникает следующая комбинаторная задача:

Сколькими различными способами можно расставить n ладей на доске n×n так, чтобы они держали под угрозой все поля доски?

Если n ладей угрожают всем полям доски, то либо на каждой ее вертикали, либо на каждой горизонтали стоит по одной ладье (если бы существовали вертикаль и горизонталь, свободные от ладей, то поле, находящееся па их пересечении, не было бы атаковано). Число расстановок n ладей по одной на каждой вертикали (или на каждой горизонтали) равно nⁿ (первую ладью можно поставить n способами на одно из полей первой вертикали; вторую, независимо от первой, n способами на одно иг полей второй вертикали и т. д.). На первый взгляд кажется, что общее число расположений равно nⁿ + nⁿ = 2nⁿ. Однако при таком подсчете по два раза учтены все расположения, в которых на каждой вертикали и горизонтали стоит по одной ладье, и число таких расположений надо вычесть. Так как каждое из них характеризуется тем, что никакая пара ладей не угрожает друг другу, то решением задачи является число 2nⁿ - n! Для обычной доски число расстановок восьми ладей, обстреливающих все ее поля, равно 2×8⁸ - 8! = 33514312.

Рис. 32. Маршруты ладьи на шахматной доске

Исследуя свойства «коня-коммивояжера», мы видели, что найти обходной маршрут для него не так-то легко. Что же касается ладьи, то ее «неповоротливость» заметно упрощает дело. Два несложных маршрута показаны на рис. 32, причем первый из них является замкнутым. Так же как и для коней, на нечетных досках замкнутого маршрута ладьи не существует, поскольку черные и белые поля в таком маршруте чередуются и их число должно быть четным.

Пусть ладья обошла все поля доски n×n28. Какое наименьшее число поворотов при этом она могла сделать?

Будем говорить, что ладья движется вдоль горизонтали (вертикали), если при своем ходе она перемещается с одного поля этой горизонтали (вертикали) на другое. При обходе доски ладья должна хотя бы раз двигаться вдоль каждой вертикали или вдоль каждой горизонтали (если найдется вертикаль, вдоль которой ладья ни разу не двигалась, то каждое ее поле ладья проходила, двигаясь «поперек», т. е. вдоль соответствующей горизонтали). Пусть, для определенности, ладья двигалась хотя бы один раз вдоль каждой вертикали. На любую из этих вертикалей (кроме, быть может, той, с которой начинается обход, и той, на которой обход заканчивается) ладья должна войти и после движения вдоль нее выйти. При этом вход и выход обязательно осуществляются с поворотами. Таким образом, общее число* поворотов не меньше, чем (n - 2)×2 + 1 + 1 = 2 (n - 1). Для любого n маршрут, содержащий ровно 2 (n - 1) поворотов, можно получить из второго маршрута на рис. 32; в данном случае (n = 8) ладья делает 2 (8 - 1) = 14 поворотов.

Так как при посещении ладьей всех полей доски число ее ходов на единицу больше числа поворотов, то минимальное число ходов, за которое она может обойти доску, равно 2 (n - 1) + 1 = 2n - 1. Из этого следует, что второй маршрут на рис. 32 является кратчайшим на обычной доске (он состоит из 15 ходов). Замкнутый маршрут уже содержит на один ход больше.

Итак, с маршрутами ладьи у нас имеется полная ясность. Рассмотрим теперь несколько задач о ладье, которые по типу отличаются от предыдущих.

В задаче на рис. 33 следует дать мат черному королю, удовлетворяя трем условиям: а) мат ставит ладья с номером 8, б) в процессе решения ладьи не покидают выделенный квадрат (кроме последнего хода); в) в заключительной позиции ладьи расположены по кругу в той жо последовательности, что и в исходной позиции.

Вообще говоря, мат здесь дается первым же ходом после Лd5:d6. Однако дополнительные условия настолько усложняют дело, что мат удается объявить только на 32 (!) ходу. Приведем номера ладей, которые совершают ходы (у черного короля выбор невелик - с d7 на d8 и обратно): 5, 6, 7, 5, б, 4, 3, б, 4, 7, 5, 4, 7, 3, 6, 7, 3, 5, 4, 3, 1, 8, 2, 4, 5,6,7, 1, 8, 2, 1, и ладья с номером 8 берет слона с матом.

Рис. 33. Мат ладьей номер 8; ладьи располагаются по кругу в том же порядке

Король-самоубийца. На доске 1000×1000 стоят белый король и 499 черных ладей. Доказать, что при произвольном начальном расположении этих фигур король за некоторое число ходов может встать под шах, как бы черные ни играли.

Пошлем короля сначала в левый нижний угол доски и затем по главной диагонали вправо вверх. Можно считать, что после первого хода короля из угла (Крa1-b2) и ответного хода черных три нижние горизонтали и три левые вертикали свободны от ладей, иначе уже вторым ходом король встанет под шах. Таким образом, все ладьи находятся выше и правее короля. Рассмотрим теперь тот момент, когда король сделал еще 997 ходов по главной диагонали и черные ответили на его последний ход. При этом ни одна из ладей не должна находиться на трех верхних горизонталях и трех правых вертикалях. Иначе говоря, все ладьи расположены левее и ниже короля (иначе он следующим ходом опять добьется своей цели). Это означает, что к рассматриваемому моменту каждая ладья должна была сделать два хода, поменяв свою вертикаль и горизонталь до того, как на них появится король. Но ладей имеется 499 и за 997 ходов им не переместиться - не хватает ровно одного хода!

Еще одна интересная задача, в которой участвуют одновременно ладья и король, принадлежит Штейнгаузу29.

Заминированная доска. Некоторые псля доски «заминированы» так, что король не может попасаь с вертикали а на вертикаль h. Доказать, что в этом случае ладья может пройти с первой горизонтали на восьмую го одним «заминированным» полям.

Будем считать, что все заминированные поля существенны, т. е. при разминировании хотя бы одного из них король прорывается с края на край (в противном случае часть полей разминируем). Можно убедиться, что тогда всякое заминированное поле, не являющееся граничным, примыкает к двум другим заминированным полям; кроме того, на крайних вертикалях заминированных полей вообще нет, а заминированные поля крайних горизонталей примыкают только к таким же полям соседних горизонталей. Это означает, что на доске имеется «мост» между крайними горизонталями, состоящий из заминированных полей (ладья сразу переходит с первой горизонтали на вторую, затем проходит некоторое число полей, быть может 0, по второй горизонтали, переходит на третью и т. д.). Любопытно, что за полное решение этой задачи редакция польского журнала «Математика», по совету Штейнгауза, назначила 20 очков (вместо первоначальных

3), но… решения так и не последовало!

Уберем теперь королей с доски и продолжим наш рассказ о ладьях с формулировки еще одной, довольно сложной задачи Штейнгауза, решение которой можно найти в первой из названных книг.

Возьмем доску n×n, отличающуюся от обычной раскраской, а именно: распределение черных и белых полей произвольно, лишь бы на каждой вертикали было хотя бы одно белое поле и хотя бы одна вертикаль состояла целиком из белых полей. Доказать, что на такой доске можно расставить некоторое количество ладей, удовлетворяющих следующим условиям:

1) ладьи стоят только на белых полях;

2) на доске находится, по крайней мере, одна ладья;

3) ладьи не атакуют друг друга;

4) если свободное белое поле атакуется ладьей по горизонтали, то оно атакуется и по вертикали.

На каждом поле доски n×n записывается произведение номеров гориэттали и вертикали, которым принадлежит это поле. Требуется расставить n ладей, не угрожающих друг другу, так, чтобы сумма чисел на полях, занимаемых ими, была наибольшей.

Ладьи следует расположить на главной диагонали (для обычной доски на полях a1, b2, c3, d4, e5, f6, g7, h8). Докажем это от противного. Пусть в оптимальном решении имеются ладьи, не стоящие на главной диагонали. Обозначим через i номер самой первой вертикали с такой ладьей, а через р - номер соответствующей горизонтали; очевидно, р > i (рис. 34,а). На каждой горизонтали должна стоять ровно одна ладья; пусть j - номер вертикали, на которой стоит ладья i-й горизонтали. Эта ладья также стоит вне главной диагонали и находится правее первой, т. е. j > i.

Переставим теперь две наши ладьи следующим образом. Оставляя их на своих вертикалях, первую поставим на i-ю горизонталь (диагональное поле), а вторую на р-ю (при этом ладьи останутся на своих вертикалях, но «обменяются» горизонталями - рис. 34,б). Ясно, что при новой расстановке они по-прежнему не угрожают друг другу. Подсчитаем суммы чисел (при обоих расположениях) для двух переместившихся ладей - остальные слагаемые при перестановке не меняются. В исходной расстановке сумма равна ip + ji, а в новой равна i² + jp. Так как j, р > i, то имеем

(i² + jp) - (ip + ji) = (jp - ip) - (ji - i²) = р(j - i) - i(j - i) = (р - i)(j - i) > 0.

Таким образом, во втором случае сумма больше, а это противоречит предположению о том, что исходное решение оптимально. Заметим, что, по существу, мы здесь использовали так называемый перестановочный прием, встречающийся при решении различных оптимизационных задач (например, в теории расписаний). Этот прием заключается в следующем: мы предполагаем, что кекоторое расположение объектов (порядок) является наилучшим в том или ином смысле, а затем, переставляя объекты, улучшаем расположение, т. е. приходим к противоречию.

На 64 полях шахматной доски выписаны подряд числа от 1 до 64 (в верхней горизонтали слева неправо - от 1 до 8, в следующей - от 9 до 16 и т. д.). Поставим на доске восемь не угрожающих друг другу ладей. Какие значения может принимать сумма чисел на полях, заняпых ладьями?

Число, стоящее на i-й вертикали и j-й горизонтали, можно записать так: i + 8(j - 1) (i, j = 1, 2, …, 8). Поскольку ладьи не угрожают друг другу, на хаждой вертикали и горизонтали стоит только одна из них. Это означает, что искомая сумма равна

и не зависит от конкретного расположения не угрожающих друг другу ладей. Задача легко обобпается для доски n×n.

Хотя ладья со своей «прямолинейноыью» уступает в хитрости коню, тем не менее в шахматно! математике, как мы видим, она занимает достойное мест). Следующая задача получила приз на шахматно-математическом конкурсе в 1960 г.30

На полях a1 и h1 стоят белые ладьи, а на полях a8 и h8 - черные. Сколькими способами могут кратчайшим путем поменяться местами белые и черные ладьи?

Кратчайшая перестановка осуществляется за четыре хода белых и черных, например:
1. Лa1-d1 Лa8-a1
2. Лd1-d8 Лh8-g8
3. Лd8-a8 Лg8-g1
4. Лh1-h8 Лg1-h1.

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

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

23. Дж. Риордан. Введение в комбинаторный анализ. М., ИЛ, 1963.

24. Примеры из теории групп можно найти у Крайчика, а из теории чисел - у Окунева.

25.. Конечно, в шахматном смысле фигуры одного цвета не угрожают друг другу. И в том случае, когда мы говорим (пользуясь общепринятой терминологией), что две фигуры угрожают друг другу (находятся под ударом, атакуют), имеется в виду лишь то, что поля, на которых они расположены, связавы между собой ходом этих фигур.

26. Начиная с этой главы, мы будем рассматривать задачи, в которых тех или иных фигур явно больше, чем в одном комплекте шахмат. В этом случае можно, как правило, обойтись пешками, наделив их привилегиями соответствующих фигур (в последней задаче - ладей).

27. Если не оговорено противное, то в такого сорта задачах мы всюду подразумеваем поля доски, свободные от уже расставленных фигур (в данном случае ладей).

28. Мы не требуем, чтобы ладья при обходе останавливалась на каждом поле доски, лишь бы она проходила мимо всех ее полей (то же самое касается ферзя и слона, о маршрутах которых речь пойдет ниже).

29. Г. Штейнгауз. Задачи и размышления. М., «Мир», 1974. Шахматно-математические задачи этого известного польского популяризатора математики можно найти также в его книгах «Математический калейдоскоп» (М. - Л., Гостехтеоретиздат, 1949) и «Сто задач» (М., Физматгиз, 1959).

30. В этом конкурсе, посвященном 25-летию союза финских проблемистов, участвовало 150 задач от 42 авторов из 15 стран. Подобные конкурсы постоянно проводятся в Югославии, Финляндии, ФРГ и в других странах.