Прямолинейная ладья

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

r0+r1x+r2x2+ј+rkxk+ј+rnxn,

где r_k — число расстановок k ладей, не угрожающих друг другу на доске nґn (k Ј n)¹. Этот многочлен и называется ладейным, он возникает при решении задач по комбинаторике, теории групп, теории чисел. Приведем один известный пример из области комбинаторики.

Пусть требуется назначить n рабочих на n различных работ, причем каждая работа должна выполняться только одним рабочим. Сколькими способами можно осуществить такое назначение?

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

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

Фактически в этой задаче требуется найти число r_n — коэффициент при старшем члене ладейного многочлена. Прежде чем провести вычисления, заметим, что при любой расположении более n ладей найдется хотя бы одна вертикаль и хотя бы одна горизонталь с двумя или более ладьями, т.е. n — это наибольшее число мирных ладей на доске nґn. Одна из расстановок восьми мирных ладей на обычной доске приведена на рис. 25².

Рис. 25. Восемь мирных ладей.

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

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

Итак, n рабочих можно назначить на n работ n! различными способами. Пусть выбрано назначение, соответствующее рис. 25, т.е. i-го рабочего назначили на i-ую работу, и требуется сделать новое назначение с учетом того, что каждый рабочий хочет поменять свою предыдущую работу. Сколько существует таких назначений? Эта задача имеет иную ладейную формулировку.

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

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

An=n! ж з и 1 2! - 1 3! + 1 4! -ј+ (-1)n n! ц ч ш .

Для n=8 получаем A₈=14833, т.е. при дополнительном условии число расстановок восьми ладей, не угрожающих друг другу, уменьшается почти втрое.

В рассмотренных задачах о ладьях, как и в аналогичных задачах для других фигур, обычно предполагается, что все они одного цвета. Если расставлять и белые, и черные фигуры, то число расстановок увеличивается.

Сколькими способами можно расставить n мирных ладей на доске nґn, если k из них — белые и n-k — черные?

Всякая расстановка, удовлетворяющая условиям задачи, определяется выбором n полей для всех n мирных ладей и затем указанием k полей из этих n, на которых будут расположены белые ладьи, остальные n-k полей займут черные ладьи. Таким образом, искомое число расстановок равно n! C_n^k.

Рассмотрим снова расстановку на рис. 25. Мы видим, что восемь ладей способны взять под обстрел все поля шахматной доски. Соответственно, для охраны всей доски nґn достаточно иметь n ладей. Если ладей меньше, чем n, то по крайней мере одна ее вертикаль и одна горизонталь окажутся пустыми и, значит, поле, стоящее на их пересечении, не будет атаковано.

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

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

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

В задачах о расстановке мирных ладей мы могли использовать всю доску. Предположим теперь, что имеется ряд запрещенных полей, на которые ладьи ставить нельзя. В этом случае установлены следующие интересные факты. Если на каждой вертикали и на каждой горизонтали доски nґn имеется хотя бы по два поля, доступные ладьям, то существует не менее двух различных расстановок n мирных ладей. При этом на доске n×n можно расставить одновременно n белых ладей, не атакующих друг друга, и n черных, обладающих тем же свойством. Если каждая вертикаль и горизонталь доски содержит ровно два свободных поля (а всего на доске 2n полей), то число расположений n мирных ладей равно 2^b, где b Ј [n/2] (квадратные скобки означают целую часть числа).

Проиллюстрируем сказанное на примере обычной доски (рис. 26,а). Каждая линия доски содержит по два разрешенных поля, а остальные являются запрещенными. Совокупность всех 16 полей разбита на четыре квадрата 2ґ2, и в каждом из них можно поставить две мирные ладьи одним из двух способов (a1, b2 или a2, b1 для левого нижнего квадрата; c3, d4 или c4, d3 для следующего квадрата и т.д.). Таким образом, всего имеется 2^b=2⁴=16 различных расположений мирных ладей, а поскольку b Ј n/2=4, это — максимально возможное число. Простейшее, диагональное расположение ладей дано на рис. 25. Минимальный вариант представлен на рис. 26,б. Здесь существуют лишь две расстановки — одна диагональная, а в другой ладьи занимают все поля, лежащие вне диагонали.

Рис. 26. Доски с запрещенными полями.

В следующей задаче о ладье (и короле) часть полей также является запрещенной.

Пусть некоторые поля доски nґn заминированы таким образом, что король не может пройти с одной крайней вертикали на другую. Доказать, что в этом случае ладья может пройти с одной крайней горизонтали на другую (с первой на последнюю) по одним заминированным полям.

На рис. 27 заминированные поля доски выделены черной краской, и они преграждают королю путь между крайними вертикалями. По мосту, состоящему из одних заминированных полей, ладья может пройти с первой горизонтали доски (поле b1) на последнюю (поле g8).

Рис. 27. Ладья на заминированной доске.

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

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

Убедимся, что указанным образом можно расположить не более 4n/3 ладей. Пусть на доске расставлены k ладей, удовлетворяющих условию задачи. На всех занятых ладьями полях напишем сначала число 0, а затем с каждой из n вертикалей доски проделаем следующую операцию. Если на ней стоят две ладьи, то к числам на полях с ладьями прибавим 1, а если стоит одна ладья, то прибавим 2. Теперь такую же операцию проделаем с каждой из n горизонталей доски. В результате на каждом из k полей с ладьями будет написано число 3 или 4, и поэтому сумма s всех чисел не меньше 3k. С другой стороны, поскольку на каждой из n вертикалей и n горизонталей доски мы добавили не более двух единиц, s не больше 4n. Итак, 3k Ј s Ј 4n, откуда k Ј 4n/3. Таким образом, максимально возможное числа ладей равно [4n/3], причем эта оценка является достижимой. Для n=8 имеем [4n/3]=10, и соответствующее расположение десяти ладей показано на рис. 28,а (оно легко обобщается для любого n). Расстановка десяти ферзей, обладающих тем же свойством — каждый из ферзей под ударом только одного другого, показана на рис. 28,б. В отличие от ладей, для ферзей задача в общем случае не решена.

Рис. 28. Пять пар ладей и ферзей.

Вернемся к расстановкам мирных ладей на шахматной доске.

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

Ладьи следует расположить вдоль главной диагонали (см. рис. 25). Докажем это от противного. Пусть в искомом решении имеются ладьи, не стоящие на главной диагонали. Обозначим через i номер самой первой вертикали с такой ладьей, а через p — номер соответствующей горизонтали; очевидно, p > i (рис. 29,а). Пусть j — номер вертикали, на которой стоит ладья i-й горизонтали. Эта ладья также стоит вне главной диагонали и находится правее первой, т.е. j > i. Переставим две эти ладьи — оставляя на своих вертикалях, поменяем их горизонтали. В результате первая из этих ладей окажется на i-й горизонтали (диагональное поле), а вторая на p-й (рис. 29,б). Ясно, что ладьи по-прежнему не угрожают друг другу.

Рис. 29. Перестановочный прием.

Подсчитаем суммы чисел для обоих расположений соответствующие двум переместившимся ладьям (на остальные слагаемые перестановка не влияет). Для исходной расстановки суммы была равна ip+ji, а для новой — i²+jp. Так как j, p > 1, то имеем

(i2+ip) - (ip+ji) = (jp-ip) - (ji-i2) = p(j-i) - i(j-i) = (p-i)(j-i) > 0.

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

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

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

8 е i=1  + 8 е j=1  8(j-1) = (1+2+ј+8)+8(0+1+ј+7) = 260 (магическому числу!)

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

На доске nґn расставлены ладьи, удовлетворяющие следующему условию: если некоторое поле свободно, то общее число ладей, стоящих на одной горизонтали и одной вертикали с ним, не меньше n. Доказать, что на доске находится не менее n²/2 ладей.

Рассмотрим ту из 2n линий доски, на которой стоит меньше всего ладей (если таких линий несколько, выберем любую из них). Пусть эта линия-горизонталь (в противном случае можно повернуть доску на 90^°), и на ней стоит k ладей. Если k і n/2, то на каждой из n горизонталей не менее n/2 ладей, а всего на доске не менее n²/2 ладей, и все доказано.

Предположим теперь, что k < n/2. На данной горизонтали имеется n-k свободных полей, и каждая вертикаль, проходящая через это свободное поле, содержит, по условию задачи, не менее n-k ладей, а все вертикали вместе — не менее (n-k)² ладей. Остальные k вертикалей имеют не менее k ладей каждая (ввиду выбора числа k). Итак, всего на доске стоит не менее (n-k)²+k² ладей. Нам осталось доказать неравенство: (n-k)²+k² і n²/2. Это можно сделать разными способами, например, так:

(n-k)2+k2-n2/2=n2/2-2nk+2k2=2(n2/4-nk+k2) = 2(n/2-k)2 > 0.

Если n четно, то, поставив ладьи на все одноцветные поля доски, получим расстановку, содержащую ровно n²/2 ладей. Если n нечетно, то можно расставить (n²+1)/2 ладей — на все поля того цвета, которого на доске больше.

Нам осталось обсудить вопрос о путешествиях ладьи по шахматной доске. Если маршрут коня находился непросто, то для прямолинейной ладьи никаких сложностей нет. На рис. 30 показаны два маршрута ладьи — открытый (рис. 30,а) и замкнутый (рис. 30,б). Первый из них обобщается для любой доски nґn. Что касается замкнутого маршрута, то для его существования, как и в задаче о коне, необходимо, чтобы доска была четна — белые и черные поля в таком маршруте чередуются, и общее число их четно.

Рис. 30. Маршруты ладьи по доске.

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

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

Так как число ходов ладьи на единицу больше числа поворотов, то самый быстрый маршрут по доске nґn состоит из 2(n-2)+1=2n-1 ходов; для любого n его также можно получить из рис. 30,а. В частности, обычную доску ладья обходит за 15 ходов. Этот маршрут является открытым, замкнутый маршрут состоит уже из 16 ходов (рис. 30,б).

Примечания:

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

²Начиная с этой главы, мы будем часто встречаться с задачами, в которых тех или иных фигур явно больше, чем в одном шахматном комплекте. В этом случае вместо расстановки фигур на доске удобнее рисовать их прямо на диаграммах.

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

| Оглавление |