Сколькими способами можно расположить 8 ладей

Глава 6. Неповоротливая ладья / Математика на шахматной доске

Гик Е. Я.

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

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

где 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 n + n n = 2n n . Однако при таком подсчете по два раза учтены все расположения, в которых на каждой вертикали и горизонтали стоит по одной ладье, и число таких расположений надо вычесть. Так как каждое из них характеризуется тем, что никакая пара ладей не угрожает друг другу, то решением задачи является число 2n n — n! Для обычной доски число расстановок восьми ладей, обстреливающих все ее поля, равно 2×8 8 — 8! = 33514312.

Исследуя свойства «коня-коммивояжера», мы видели, что найти обходной маршрут для него не так-то легко. Что же касается ладьи, то ее «неповоротливость» заметно упрощает дело. Два несложных маршрута показаны на рис. 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 берет слона с матом. Король-самоубийца. На доске 1000×1000 стоят белый король и 499 черных ладей. Доказать, что при произвольном начальном расположении этих фигур король за некоторое число ходов может встать под шах, как бы черные ни играли. Пошлем короля сначала в левый нижний угол доски и затем по главной диагонали вправо вверх. Можно считать, что после первого хода короля из угла (Крa1-b2) и ответного хода черных три нижние горизонтали и три левые вертикали свободны от ладей, иначе уже вторым ходом король встанет под шах. Таким образом, все ладьи находятся выше и правее короля. Рассмотрим теперь тот момент, когда король сделал еще 997 ходов по главной диагонали и черные ответили на его последний ход. При этом ни одна из ладей не должна находиться на трех верхних горизонталях и трех правых вертикалях. Иначе говоря, все ладьи расположены левее и ниже короля (иначе он следующим ходом опять добьется своей цели). Это означает, что к рассматриваемому моменту каждая ладья должна была сделать два хода, поменяв свою вертикаль и горизонталь до того, как на них появится король. Но ладей имеется 499 и за 997 ходов им не переместиться — не хватает ровно одного хода! Еще одна интересная задача, в которой участвуют одновременно ладья и король, принадлежит Штейнгаузу29. Заминированная доска. Некоторые псля доски «заминированы» так, что король не может попасаь с вертикали а на вертикаль h. Доказать, что в этом случае ладья может пройти с первой горизонтали на восьмую го одним «заминированным» полям. Будем считать, что все заминированные поля существенны, т. е. при разминировании хотя бы одного из них король прорывается с края на край (в противном случае часть полей разминируем). Можно убедиться, что тогда всякое заминированное поле, не являющееся граничным, примыкает к двум другим заминированным полям; кроме того, на крайних вертикалях заминированных полей вообще нет, а заминированные поля крайних горизонталей примыкают только к таким же полям соседних горизонталей. Это означает, что на доске имеется «мост» между крайними горизонталями, состоящий из заминированных полей (ладья сразу переходит с первой горизонтали на вторую, затем проходит некоторое число полей, быть может 0, по второй горизонтали, переходит на третью и т. д.). Любопытно, что за полное решение этой задачи редакция польского журнала «Математика», по совету Штейнгауза, назначила 20 очков (вместо первоначальных 3), но… решения так и не последовало! Уберем теперь королей с доски и продолжим наш рассказ о ладьях с формулировки еще одной, довольно сложной задачи Штейнгауза, решение которой можно найти в первой из названных книг. Возьмем доску n×n, отличающуюся от обычной раскраской, а именно: распределение черных и белых полей произвольно, лишь бы на каждой вертикали было хотя бы одно белое поле и хотя бы одна вертикаль состояла целиком из белых полей. Доказать, что на такой доске можно расставить некоторое количество ладей, удовлетворяющих следующим условиям: 1) ладьи стоят только на белых полях; 2) на доске находится, по крайней мере, одна ладья; 3) ладьи не атакуют друг друга; 4) если свободное белое поле атакуется ладьей по горизонтали, то оно атакуется и по вертикали. На каждом поле доски n×n записывается произведение номеров гориэттали и вертикали, которым принадлежит это поле. Требуется расставить n ладей, не угрожающих друг другу, так, чтобы сумма чисел на полях, занимаемых ими, была наибольшей. Источник Читайте также:  Гербалайф растительный напиток алоэ классический способ применения Оцените статью Вам также может понравиться Ясень семена способ распространения Ясень обыкновенный Fraxinus excelsior – так в ботанической Ярлыки способы создания ярлыков ос windows Создаем ярлыки на рабочем столе Windows Создаем ярлыки Японское удобрение фуджима способ применения Удобрения Фуджима Знаете потрясающее удобрение, палочка Японский чай способ заварки Технология заваривания японского чая Известно, что Правообладателям Политика конфиденциальности Контакты