Сколькими способами можно поставить 2 ладьи чтобы они не били друг друга

Сколькими способами можно поставить 2 ладьи чтобы они не били друг друга

а) Поставим сначала чёрную ладью. Это можно сделать 8 · 8 = 64 способами. Чтобы белая ладья её не била, надо поставить её в другие горизонталь и вертикаль, то есть свободных для неё горизонталей будет 8 — 1 = 7, и вертикалей тоже 8 — 1 = 7. То есть, поставить белую ладью при уже поставленной чёрной можно 7 · 7 = 49 способами. Так как на каждый из 64 способов поставить чёрную ладью будет 49 способов поставить белую, то всего способов поставить обе будет 64 · 49 = 3136.

б) Поставим сначала чёрного короля. Сколько способов тогда останется для постановки белого? Рассмотрим разные случаи:

Если чёрный король стоит в углу доски, то белого нельзя ставить на 4 клетки, то есть можно поставить на одну из 8·8 — 4 = 60 клеток. Углов в доске 4, то есть таких случаев, когда чёрный король стоит в углу, а белый его не бьёт, 4 · 60 = 240.

Дальше, если чёрный король стоит с краю доски (не в углу), то белого нельзя ставить на 6 клеток, то есть можно ставить на 64 — 6 = 58 клеток. На каждой из 4 сторон доски есть 8 — 2 = 6 клеток, где чёрный король будет стоять с краю, но не в углу, то есть всего таких вариантов растановки обоих королей будет 4 · 6 · 58 = 1392.

Наконец, если чёрный король стоит на внутренней клетке доски (они образуют квадрат со стороной 8 — 2 = 6, поэтому внутренних клеток будет 6 · 6 = 36), то белого можно поставить на одну из 64 — 9 = 55 клеток. Всего вариантов расстановки, где чёрный король стоит на внутренней клетке, будет 36 · 55 = 1980.

Итак, всего подходящих вариантов будет 240 + 1392 + 1980 = (200 + 40) + (1400 — 8) + (2000 — 20) = 1600 + 2000 + (40 — 20 — 8) = 3600 + 12 = 3612

Источник

Ладейные числа (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6

ЛАДЕЙНЫЕ ЧИСЛА. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ.

Рассмотрим обычную шахматную доску и обычную шахматную фигуру — ладью. Сколькими способами можно поставить на шахматную доску две ладьи так, чтобы они не били друг друга? Какое наибольшее число ладей можно поставить на доску так, чтобы каждая ладья била не более двух других? Можно задать много подобных вопросов, наверняка читатель встречал такого рода задачи на олимпиадах или в книжках по развлекательной математике(см., например, книгу [1]).

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

ладейных чисел. Для начала несколько определений.

Пусть дана бесконечная клетчатая плоскость. Доской будем называть произвольный конечный набор клеток этой плоскости.

Ладья — это фигура, которая держит под боем все клетки плоскости, находящиеся с ней на одной горизонтали или на одной вертикали.

Таким образом, для досок сложной формы ладья может держать под боем клетки, отделённые от неё клетками, не принадлежащими доске. Так, на рис. 1 изображена несвязная доска из пяти клеток, ладья и клетки, находящиеся под боем этой ладьи (отмечены крестиками).

Зафиксируем произвольную доску B и для каждого натурального вычислим количество различных способов поставить на эту доску не бьющих друг друга ладей. Обозначим это количество или , если нужно указать, о какой именно доске идёт речь. Положим по определению. Числа называются ладейными числами доски B.

Очевидно, что, где S—площадь (количество клеток) доски B.

Если же мы хотим разместить на доске слишком много ладей — больше S — у нас ничего не получится: все ладьи не поместятся на нашу доску. Таким образом, для любой доски ладейные числа с большими номерами равны нулю.

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

Для вычисления ладейных чисел часто хватает несложных комбинаторных соображений. Найдём, например, чему равно число для обычной шахматной доски 88. Трёх ладей на доске можно расставить 3! способами. Чтобы расставить три ладьи на доске 88, достаточно сначала выбрать три вертикали и три горизонтали —

это можно сделать способами, а потом на образовавшейся доске взять одну из шести расстановок. Итак, для шахматной доски .

Приведём ещё один пример.

Лемма I. Пусть имеется доска B и — произвольная клетка. Пусть Крест() — это множество клеток доски B, лежащих на той же горизонтали или в той же вертикали, что и клетка .

(1)

(Здесь мы используем обычные обозначения: — это доска, полученная из B удалением клетки.)

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

Заметим, что утверждение Лемма I показывает, как можно вычислить ладейные числа какой-нибудь доски, если известны ладейные числа меньших досок. Таким образом, на самом деле равенство (1) — это рекуррентная формула, с помощью которой мы можем вычислять ладейные числа любой доски B (лучше на компьютере), не пользуясь никакими комбинаторными идеями.

Правда, придётся накопить довольно много информации о ладейных числах досок, которые содержатся в . Примеры других рекуррентных формул мы встретим в § 3.

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

Изучая ладейные числа различных досок, хотелось бы научиться для каждой доски подбирать эквивалентную доску «достаточно простой» формы. Естественный и простой способ преобразовать доску так, чтобы её ладейные числа не изменились, состоит в перестановке вертикальных или горизонтальных рядов клеток, составляющих эту доску. Так, для доски на рис. 1, переставляя вертикальный ряд клеток, содержащий изолированную клетку, «поближе» к «основной части» доски, мы можем получить связную доску

что, по-видимому, можно рассматривать как «упрощение» формы. Другими естественными операциями над досками, сохраняющими ладейные числа, являются поворот на ± или и отражения доски относительно вертикали, горизонтали или диагонали.

Хотя эти операции и позволяют изменять форму доски, добиться «совсем простой» формы, пользуясь этими или ещё какими-нибудь операциями, видимо, не удастся, что видно уже на примере всё тех же пятиклеточных досок.

Но все же мы будем рассматривать достаточно богатый класс досок относительно простой формы. Это так называемые диаграммы Юнга.

Диаграмма Юнга со строками — это доска, горизонтали которой выровнены пo левому краю и содержат соответственно клеток (снизу вверх). Иногда мы будем считать, что диаграмма Юнга может иметь нулевые строки. На рис. 3 изображены две диаграммы Юнга: квадрат (а) и диаграмма Юнга со строками 1, 3, 5, 7 (б).

В заключение этого параграфа приведём нетривиальный пример двух эквивалентных досок.

Теорема I. Квадратная доска эквивалентна доске в форме диаграммы Юнга с длинами строк 1, 3, 5, . 2n−1.

Доказательство. Обозначим квадрат через . Мы построим по индукции взаимно однозначное соответствие между расстановками ладей в и в , следуя А. Левиту.

База индукции n=1 очевидна. Докажем индукционный переход. Разобьём квадрат на две части: квадрат и «рамку», состоящую из 2n−1 клеток. Треугольную доску тоже разобьём на две части: доску и самую длинную горизонталь (тоже из 2n−1 клеток). Допустим, что совпадение ладейных чисел квадрата и треугольника уже установлено. Тогда можно считать, что построено соответствие между расстановками ладей в квадрате , в которых все ладьи находятся в выделенной части , и расстановками ладей в , в которых все ладьи находятся в выделенной части . Осталось построить соответствие между расстановками ладей в , которые содержат ладью на длинной горизонтали, и расстановками ладей в , которые содержат ладьи в «рамке». Рассмотрим все расстановки ладей в , содержащие ладью в длинной строке, у которых расстановка k−1 ладей в фиксирована, назовём её , а соответствующую ей расстановку в назовём . Всего имеется таких расстановок, поскольку в длинной строке ровно столько подходящих для последней ладьи клеток. Пронумеруем как-нибудь эти клетки (рис. 4).

Источник