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

Задачи 851-865

851. Сколько существует способов разместить две ладьи на шахматной доске, так, чтобы они не смогли сбить друг друга?

Решение. Заметим, что возможность сбить друг друга у ладей «взаимная», т. е. если первая ладья сможет сбить вторую, то вторая сможет сбить первую, и наоборот. Одну ладью можно поставить на любую из 64-х клеток шахматной доски (64 способа). При этом 1 клетка будет занята а еще 14 окажутся под боем — 7 на вертикали и 7 на горизонтали. Следовательно, для второй ладьи останется 64 — (1+7+7) = 49 мест (49 способов поставить вторую ладью). Для каждого из 64 способов разместить одну ладью существует 49 спобов разместить вторую, значит разместить две ладьи можно 64· 49 = 3136 способами.

852. В расписании 7-А класса на четверг могут произойти следующие изменения:
1) на 5-м уроке вместо урока труда может быть русский язык, русская литература, история или география;
2) на 6-м уроке вместо урока труда может быть история, география, физика, биология или черчение.
Сколько существует возможных вариантов расписания уроков для 7-А на четверг?

Решение. Заменить 5-й урок, по условию задачи, можно 4-мя способами, при этом для любого предмета на 5-ом уроке существует 5 способов заменить 6-й урок. Следовательно, заменить оба урока можно 4· 5 = 20 способами.

853. Чемпионат, в котором участвуют 16 команд, проводится в два круга. Определить какое количество матчей необходимо провести, чтобы каждая команда сыграла с каждой ровно два раза.

Решение. Каждая из 16 команд должна сыграть по одному матчу с каждой из оставшихся 15 команд. То есть, 16 команд проведут по 15 матчей, всего 16· 15 = 240 матчей. При таком подсчете матч некоторой команды N с командой M учитывается среди 15 матчей команды N, но ответный матч команды M с командой N учтен среди 15 матчей команды M, следовательно, каждая пара команд встретится дважды.

854. Сколько двенадцатизначных чисел можно составить из цифр 1, 2 та 3 так, чтобы каждые две соседние цифры отличались ровно на единицу?

Решение. Так как соседние цифри числа должны отличаться ровно на 1, то цифры 1 и 3 не могут быть соседними. То есть после цифры 1 обязательно должна следовать цифра 2, и после цифры 3 — тоже только цифра 2. Следовательно, все такие 12-цифровые числа можно разделить на две группы:
1. числа, начинающиеся с 1 или 3 и содержашие на четных позициях только цифру 2, а на нечетных либо 1 либо 3,
2. числа, начинающиеся с 2 и содержашие на четных позициях только цифру 2, а на нечетных либо 1 либо 3.
Все числа из первой группы образуются из шести двоек на четных позициях, размещением на шести нечетных позициях 1 либо 3. Таких чисел получится 2· 2· 2· 2· 2· 2 = 2 6 = 64, так как на каждой из шести нечетных позиций может оказаться либо 1 либо 3. Аналогично получим 2 6 = 64 числа, начинающихся с 2. Всего 64 + 64 = 128 чисел.

855. По дороге домой Петя должен зайти в супермаркет. Из школы к супермаркету ведет 4 дороги, а от супермаркета домой можно пройти по трем различным улицам. Сколько вариантов маршрута из школы домой имеет Петя?

Решение. Если Петя пройдет к супермаркету по первой дороге, то у него останется 3 варианта маршрута, так как от супермаркета домой можно пройти по трем различным улицам. Аналогично идя в супермаркет по второй Петя имеет три варианта маршрута домой, как, впрочем, и идя по третьей или четвертой. Всего получим 3+3+3+3 = 4· 3 = 12 различных маршрутов.

856. В кассе вокзала на поезд № 91 осталось 5 купейных билетов и 8 плацкартных. Сколько способов купить билеты для компании из 4 человек (места имеют значение)?

Решение. Всего в кассе имеется 5+8=13 билетов. Первый билет можно купить 13-ю способами, останется 12 билетов. Значит, следующий билет можно купить 12-ю способами, третий — 11-ю способами, четвертый — 10-ю. Следовательно, все четыре билета можно купить 13· 12· 11· 10 = 17160 способами.

857. В шахматном турнире участвуют 23 шахматиста. Определить какое количество партий необходимо провести, чтобы каждый сыграл с каждым дважды.

Решение. Каждый из 23 участников должен сыграть по одной партии с каждым из 22 остальных. При этом партий с участием шахматиста N и шахматиста M окажется именно две: с одной стороны среди 22-х партий участника N, с другой стороны среди 22-х партий участника M. Следовательно необходимо провести 23· 22 = 506 партий.

858. Две ладьи находятся на шахматной доске так, что каждая из них может сбить другую. Сколько таких размещений?

Решение.Одну ладью можно поставить на любую из 64-х клеток шахматной доски (64 способа). Тогда, для того, чтобы ладьи смогли сбить друг друга, вторую ладью следует разместить на одной из семи свободных клеток вертикали, которую занимает первая ладья, или на одной из семи клеток горизонтали. Имеем 7 + 7 = 14 способов поставить вторую ладью. Для каждого из 64 способов разместить первую ладью существует 14 спобов разместить вторую, значит разместить две ладьи можно 64· 14 = 896 способами.

859. Расписание одного дня учебы состоит из пяти уроков. Определить количество возможных вариантов расписания, если изучается 11 различных предметов и по каждому предмету в день может быть только один урок.

Решение.1 способ. На первый урок можно выбрать один из 11 указанных предметов. Тогда на второй урок можно поставить один из оставшихся 10-ти предметов, поскольку по каждому предмету в день может быть только один урок. Следовательно, существует 11· 10 = 110 вариантов расписания на первых два урока. На третьем уроке может быть один из 9 оставшихся предметов, вариантов расписания на три урока — 11· 10· 9 = 990. На четвертый урок остается один из 8-ми предметов, на пятый — один из 7-ми. Всего вариантов расписания из пяти уроков — 11· 10· 9· 8· 7 = 55440.
2 способ. Расписание из пяти уроков можно представить как таблицу из пяти клеток, в каждую из которых можно вписать один из 11 предметов, причем одинаковых предметов не должно быть. Следовательно, мы имеем дело с таким комбинаторным объектом, как размещение без повторений из 11 элементов по 5. Количество таких размещений вычисляется по формуле

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

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

861. Замок открывается, если правильно набран определенный трехзначный код, который составлен из пяти различных цифр. Попытка состоит в наборе трех цифр наугад, без повторения набранных ранее комбинаций. Открыть замок удалось только на последней из всех возможных попыток. Сколько неудачных попыток было до этого?

Решение. Первой цифрой кода может оказаться одна из 5-ти цифр, из которых составлялся код. Второй — тоже любая цифра из этих 5-ти цифр, так же, как и третьей. Всего можно составить 5· 5· 5 = 125 всевозможных трезначных кодов. Значит, и всевозможных попыток набрать код может быть 125, так как коды при наборе не повторяют. Последняя, 125-я попытка была удачной, следовательно, неудачных попыток было 125 — 1 = 124.

862. Команда, которая состоит из 15 спортсменов, выдвигает 4 участника эстафеты 800м. + 400м. + 200м. +100м. Сколько существует способов такого выбора?

Решение. Очевидно, на каждый из 4 участков эстафеты выставляют различных спортсменов. На первый участок можно выбрать любого из 15 членов комады, на второй — любого из оставшихся 14, на третий — одного из 13, на четвертый — одного из 12. Всего 15· 14· 13· 12 = 32760.

863. Команда, состоящая из пяти человек, участвует в соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколько существует способов распределения мест, занятых спортсменами этой команды?

Решение. Всего в соревнованиях участвуют 5 + 20 = 25 спортсменов, следовательно, в итоге соревнований каждый из них займет одно из 25-ти мест. При этом каждый из пяти членов нашей команды займет свое определенной место, одно из 25 — имеем размещение без повторений из 25 элементов по 5. Количество таких размещений

864. Из 12 резервных троллейбусов в троллейбусном парке нужно выпустить на линию по одному дополнительному троллейбусу на каждый из 7 маршрутов. Сколько существует способов это сделать?

Решение. Каждому их 7 маршрутов следует выделить один из 12 имеющихся троллейбусов. Имеем размещение из 12 элементов по 7 без повторения. Без повторения, так как один троллейбус нельзя выпустить на два маршрута одновременно. Количество таких размещений:

865. Команда из трех человек участвует в соревнованиях по биатлону, в которых участвуют еще 27 спортсменов. Сколько существует способов распределения мест, занятых спортсменами команды?

Решение. Всего участников соревнований 27 + 3 = 30, следовательно они займут 30 мест с 1-го по 30-е. Если рассматривать места членов команды по очереди, то первый из них может занимать любое из 30 мест, второй — любое из 29, так как одно занято первым, третий — любое из 28, оставшихся после первых двух. Всего способов распределения мест 30· 29· 28 = 17550.
Или (см. решение задачи 863).

Источник

дискретная-математика — Сколько способов поставить k ладей на доску размера n×n?

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

задан 8 Ноя ’15 10:37

a2g
336 ● 1 ● 14 ● 69
96&#037 принятых

Число вариантов поставить первую ладью на доску размерности nxn равно n^2,число вариантов поставить вторую ладью равно (n-1)^2,число вариантов поставить третью (n-2)^2,четвертую (n-3)^2,пятую (n-4)^2,тогда ответом будет их произведение,т.е. n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2

@ivan145, тоже рассуждал так, но $% n^ <2>* (n-1)^ <2>* (n-2)^ <2>* (n-3)^ <2>* (n-4)^ <2>$% это не верный ответ.

@a2g, ответы будут отличаться в зависимости от того разными считаются ладьи или одинаковыми. Вам привели решение с разными ладьями, но если в решении нет указания на различия, то скорее всего они не различимы.

@all_exist, верно ли решение, которое привел @ivan145, если брать параметры $%k=5, n=10$% (ну и считаем что ладьи разные, хотя по условию задачи различия не делается, но мне просто для интереса)? Как мне кажется это решение только для размещения $%n$% разных ладей на доске $%n x n$%.

@a2g, Отличие в ответах при разных и одинаковых ладьях в числе перестановок. если поделите ответ @ivan145 на $%5!$%, то получите нужный ответ, совпадающий с ответом @Роман83 .

1 ответ

Понятно, что $%n\ge k$% иначе расставить ладьи не удастся. Если $%n=k$%, то ответ $%N=k!$%. Пусть теперь $%n>k=5$%. Тогда выбираем пять вертикалей, на которые можно поставить наши ладьи (ясно, что две ладьи не могут стоять на одно вертикали). Эти пять вертикалей можно выбрать $%C_n^5$% способами. На первой вертикали ладью можно разместить $%n$% способами, на второй $%- (n-1)$% способом, и т.д.

Ответ для пяти ладей: $$N=C_n^5 \cdot n \cdot (n-1) \cdot (n-2)\cdot (n-3)\cdot (n-4)$$

отвечен 8 Ноя ’15 16:20

@Роман83, формула, которую Вы привели я так понимаю для классической шахматной доски $%8×8$%? Мне не понятно откуда берется эта часть $%8⋅7⋅6⋅5⋅4$%?

Источник

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

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

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

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

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

Рис. 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!) 2 расположений ладей, не угрожающих друг другу. Это следует из того, что 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 так, чтобы они держали под обстрелом все поля доски? 3

Если n ладей охраняют доску, то либо на каждой вертикали, либо на каждой горизонтали стоит хотя бы одна из них (если существуют вертикаль и горизонталь, свободные от ладей, то поле, находящееся на их пересечении, не атаковано). Число расстановок i ладей — по одной на каждой вертикали равно n n (первую ладью можно поставить на одно из n полей первой вертикали; вторую, независимо от первой, на одно из n полей второй вертикали и т.д.). Столько же имеется расстановок и по одной на каждой горизонтали. На первый взгляд кажется, что общее число расположений ладей равно n n +n n =2n n . Однако при таком подсчете дважды учитываются расстановки, в которых на каждой вертикали и на каждой горизонтали стоит по одной ладье. Так как каждая из них характеризуется тем, что никакая пара ладей не угрожает друг другу, то решением задачи является число 2·n n — n!. Число расстановок восьми ладей, обстреливающих обычную доску, равно 2·8 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 4 =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 2 +jp. Так как j, p > 1, то имеем

(i 2 +ip) — (ip+ji) = (jp — ip) — (ji — i 2 ) = 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 /2 ладей.

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

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

(n — k) 2 +k 2 — n 2 /2=n 2 /2 — 2nk+2k 2 =2(n 2 /4 — nk+k 2 ) = 2(n/2 — k) 2 > 0.

Если n четно, то, поставив ладьи на все одноцветные поля доски, получим расстановку, содержащую ровно n 2 /2 ладей. Если n нечетно, то можно расставить (n 2 +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,б).

Примечания:

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

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

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

Источник