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

Задачи 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).

Источник

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

Найти количество способов поставить на доску восемь ладей так, чтобы никакие две не били друг друга
Дана квадратная доска 12×12 клеток. Найдите количество способов поставить на неё восемь ладей так.

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

Число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга
Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били.

Рекурсия: расставить на шахматной доске 8 ладей так, чтобы они не били друг друга
Нужно расставить на шахматной доске 8 ладей так, чтобы они не били друг друга, вот что я наваял: .

Решение

Iliodor, Странная дробь
Имхо.
а) 64*49
б) 14*49 + 50*48

Добавлено через 5 минут
в) 6*(49+8) + 8*(49+6) +49*48 (тут хорошо бы меня проверили)

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

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

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

Найдите количество способов поставить на шахматную доску 8 ладей
Дана квадратная доска 10×10 клеток. Найдите количество способов поставить на нее 8 ладей так, чтобы.

Разместить k королей так, чтобы они не били друг друга
На прямоугольном клеточном поле n x m разместить k королей так, чтобы они не били друг друга. Если.

Источник

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

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

Решение

Белую ладью можно поставить на любое из 64 полей доски, причём с каждого из них она бьёт 15 полей (включая поле, на котором стоит). Остаётся 49 полей, на которые можно поставить чёрную ладью. Итак, белую и чёрную ладью можно расставить 64·49 = 3136 способами.

Ответ

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: «АСА»
Издание	1
глава
Номер	3
Название	Комбинаторика-1
Тема	Классическая комбинаторика
задача
Номер	013
кружок
Место проведения	МЦНМО
класс
Класс	7
год
Год	2004/2005
занятие
Номер	9
задача
Номер	9.1

Проект осуществляется при поддержке и .

Источник

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

а) Поставим сначала чёрную ладью. Это можно сделать 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).

Источник