сколькими способами можно расположить 2 ладьи
Задачи 851-865
851. Сколько существует способов разместить две ладьи на шахматной доске, так, чтобы они не смогли сбить друг друга?
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 так, чтобы каждые две соседние цифры отличались ровно на единицу?
855. По дороге домой Петя должен зайти в супермаркет. Из школы к супермаркету ведет 4 дороги, а от супермаркета домой можно пройти по трем различным улицам. Сколько вариантов маршрута из школы домой имеет Петя?
Решение. Если Петя пройдет к супермаркету по первой дороге, то у него останется 3 варианта маршрута, так как от супермаркета домой можно пройти по трем различным улицам. Аналогично идя в супермаркет по второй Петя имеет три варианта маршрута домой, как, впрочем, и идя по третьей или четвертой. Всего получим 3+3+3+3 = 4· 3 = 12 различных маршрутов.
856. В кассе вокзала на поезд № 91 осталось 5 купейных билетов и 8 плацкартных. Сколько способов купить билеты для компании из 4 человек (места имеют значение)?
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 различных предметов и по каждому предмету в день может быть только один урок.
860. Иногда номера трамваев обозначают двумя цветными фонариками. Какое количество различных маршрутов можно обозначить, используя фонари восьми различных цветов.
Решение. Первый фонарь может иметь один из восьми различных цветов, при этом к каждому цвету можно добавить второй фонарь одного из восьми имеющихся цветов. Следовательно, всего можно иметь 8· 8 = 64 обозначений.
861. Замок открывается, если правильно набран определенный трехзначный код, который составлен из пяти различных цифр. Попытка состоит в наборе трех цифр наугад, без повторения набранных ранее комбинаций. Открыть замок удалось только на последней из всех возможных попыток. Сколько неудачных попыток было до этого?
862. Команда, которая состоит из 15 спортсменов, выдвигает 4 участника эстафеты 800м. + 400м. + 200м. +100м. Сколько существует способов такого выбора?
863. Команда, состоящая из пяти человек, участвует в соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколько существует способов распределения мест, занятых спортсменами этой команды?
864. Из 12 резервных троллейбусов в троллейбусном парке нужно выпустить на линию по одному дополнительному троллейбусу на каждый из 7 маршрутов. Сколько существует способов это сделать?
Решение. Каждому их 7 маршрутов следует выделить один из 12 имеющихся троллейбусов. Имеем размещение из 12 элементов по 7 без повторения. Без повторения, так как один троллейбус нельзя выпустить на два маршрута одновременно. Количество таких размещений:
865. Команда из трех человек участвует в соревнованиях по биатлону, в которых участвуют еще 27 спортсменов. Сколько существует способов распределения мест, занятых спортсменами команды?
Сколько способов поставить на шахматную доску двух ладей так, чтобы они не били друг друга?
Найти количество способов поставить на доску восемь ладей так, чтобы никакие две не били друг друга
Дана квадратная доска 12×12 клеток. Найдите количество способов поставить на неё восемь ладей так.
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга?
Помогите решить, задачу,если есть возможность объяснить первый шаг решения задачи,или общий ход.
Число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга
Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били.
Решение
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 королей так, чтобы они не били друг друга. Если.
Сколькими способами можно расположить 2 ладьи
Пусть требуется назначить n рабочих на n различных работ, причем каждая работа должна выполняться только одним рабочим. Сколькими способами можно осуществить такое назначение?
Поставим в соответствие рабочим горизонтали шахматной доски n ґ n, а работам ее вертикали. Если i-й рабочий назначается на j-ю работу, то поле, соответствующее пересечению i-й горизонтали и j-й вертикали, займем ладьей. Так как каждая работа выполняется одним рабочим и каждый рабочий назначается на одну работу, то в результате расстановки n ладей все вертикали и горизонтали доски будут содержать по одной ладье, т.е. ладьи не угрожают друг другу. Итак, нашей задаче о назначении можно придать шахматную формулировку.
Сколькими способами можно расставить n не угрожающих друг другу ладей на доске n ґ n?
Рис. 25. Восемь мирных ладей.
Если ладьи занумерованы числами от 1 до n, то существует уже (n!) 2 расположений ладей, не угрожающих друг другу. Это следует из того, что n подходящих полей можно выбрать n! способами; столько же способов имеется для расположения на этих полях n занумерованных ладей.
Итак, n рабочих можно назначить на n работ n! различными способами. Пусть выбрано назначение, соответствующее рис. 25, т.е. i-го рабочего назначили на i-ую работу, и требуется сделать новое назначение с учетом того, что каждый рабочий хочет поменять свою предыдущую работу. Сколько существует таких назначений? Эта задача имеет иную ладейную формулировку.
Сколькими способами можно расставить n не угрожающих друг другу ладей на доске n ґ n так, чтобы ни одна из них не стояла на главной диагонали (для обычной доски на диагонали a1-h8)?
Для n=8 получаем A8=14833, т.е. при дополнительном условии число расстановок восьми ладей, не угрожающих друг другу, уменьшается почти втрое.
В рассмотренных задачах о ладьях, как и в аналогичных задачах для других фигур, обычно предполагается, что все они одного цвета. Если расставлять и белые, и черные фигуры, то число расстановок увеличивается.
Сколькими способами можно расставить n ладей на доске n ґ n так, чтобы они держали под обстрелом все поля доски? 3
Комбинаторные задачи о расстановке атакующих фигур не менее популярны, чем задачи о расстановке мирных фигур. В последующих главах мы рассмотрим задачи того и другого типа для каждой шахматной фигуры. Наиболее просто они решаются для ладьи, видимо, сказывается ее прямолинейность.
Проиллюстрируем сказанное на примере обычной доски (рис. 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. Перестановочный прием.
Таким образом, во втором случае сумма больше, а это противоречит предположению о том, что исходное решение давало максимальную сумму. По существу, мы здесь использовали так называемый перестановочный прием, встречающийся при решении различных оптимизационных задач (например, в теории расписаний). Этот прием заключается в следующем: предполагается, что некоторое расположение объектов (порядок) является наилучшим в том или ином смысле, а затем при перестановке объектов расположение улучшается, т.е. получается противоречие.
На 64 полях шахматной доски выписаны подряд числа от 1 до 64 (на первой горизонтали слева направо от 1 до 8, на второй от 9 до 16 и т.д.). Поставим на доску восемь не угрожающих друг другу ладей. Какие значения может принимать сумма чисел на полях, занятых ладьями?
На доске n ґ n расставлены ладьи, удовлетворяющие следующему условию: если некоторое поле свободно, то общее число ладей, стоящих на одной горизонтали и одной вертикали с ним, не меньше n. Доказать, что на доске находится не менее n 2 /2 ладей.
Рассмотрим ту из 2n линий доски, на которой стоит меньше всего ладей (если таких линий несколько, выберем любую из них). Пусть эта линия-горизонталь (в противном случае можно повернуть доску на 90 ° ), и на ней стоит k ладей. Если k і n/2, то на каждой из n горизонталей не менее n/2 ладей, а всего на доске не менее n 2 /2 ладей, и все доказано.
Если n четно, то, поставив ладьи на все одноцветные поля доски, получим расстановку, содержащую ровно n 2 /2 ладей. Если n нечетно, то можно расставить (n 2 +1)/2 ладей на все поля того цвета, которого на доске больше.
Нам осталось обсудить вопрос о путешествиях ладьи по шахматной доске. Если маршрут коня находился непросто, то для прямолинейной ладьи никаких сложностей нет. На рис. 30 показаны два маршрута ладьи открытый (рис. 30,а) и замкнутый (рис. 30,б). Первый из них обобщается для любой доски n ґ n. Что касается замкнутого маршрута, то для его существования, как и в задаче о коне, необходимо, чтобы доска была четна белые и черные поля в таком маршруте чередуются, и общее число их четно.
Рис. 30. Маршруты ладьи по доске.
Пусть ладья обошла все поля доски n ґ n. Какое наименьшее число поворотов она могла при этом сделать?
Примечания:
1 Конечно, в шахматной игре фигуры одного цвета не угрожают друг другу. Когда мы говорим, пользуясь общепринятой терминологией, что две фигуры угрожают друг другу (находятся под ударом, атакуют), то имеем в виду лишь то, что поля, на которых они расположены, связаны между собой ходом этой фигуры. Если несколько фигур не угрожают друг другу, то мы их называем также мирными.
2 Начиная с этой главы, мы будем часто встречаться с задачами, в которых тех или иных фигур явно больше, чем в одном шахматном комплекте. В этом случае вместо расстановки фигур на доске удобнее рисовать их прямо на диаграммах.
3 В комбинаторных задачах такого типа обычно предполагается, что под угрозой находятся поля, свободные от фигур. Однако можно требовать, как в данном случае, чтобы под обстрелом находились все поля доски (и занятые, и свободные). Далее мы всюду будем оговаривать, какой из двух случаев имеется в виду.
Ответ
Да, конечно. Дело в том, что ладьи из моего шахматного комплекта оказались пронумероваными. И вот забыл их поставить нумерами вниз. 
Доказать свойство числа способов расставить на шахматной доске наибольшее число слонов
Докажите, что число способов расставить на шахматной доске наибольшее число слонов так, чтобы они.
Сколько способов выбрать на шахматной доске 7 полей?
1.17. Сколько способов выбрать на шахматной доске 7 полей так, чтобы никакие два поля не находились.
Сколько существует способов расставить?
Есть три красных, четыре синих и пять зеленых вагончиков, из которых ему хочется собрать паровозик.
Сколько существует способов
Сколько существует способов из колоды в 52 карты, если извлечь 10 карт, среди которых содержится.
Сколько существует способов распределить подарки?
4 друга собрались на Новый год. Каждый принес по подарку. Сколько существует способов распределить.
Сколько существует способов расстановки чисел
1)сколько существует способов расстановки чисел 1,2,3. так чтобы 1,2 стояли рядом и в порядке.
Сколько существует способов выхода 8 пассажиров
Лифт останавливается на 10 этажах. Сколько есть способов, которыми могут выйти из лифта 8.
Глава 6. Неповоротливая ладья / Математика на шахматной доске
Гик Е. Я.
Глава 6. Неповоротливая ладья
Ладья является самой распространенной фигурой в комбинаторных задачах на шахматной доске и часто упоминается даже в серьезной математической литературе. Что общего, скажем, между шахматным термином «ладья» и чисто математическим понятием «многочлен»? Тем не менее американский математик Дж. Риордан23 как раз применяет термин «ладейный многочлен»! Чем это вызвано? Оказывается, большой класс важных комбинаторных задач сводится к подсчету числа тех или иных расстановок ладей на шахматной доске. При рассмотрении ряда сложных задач существенную роль играет многочлен
Многие задачи из комбинаторики, теории групп и теории чисел удобно интерпретируются в «ладейных» терминах. Приведем один комбинаторный пример24. Пусть n рабочих назначаются на n различных работ, причем каждая из них должна выполняться только одним рабочим.
Спрашивается, сколькими способами можно осуществить такое назначение?
Сколькими различными способами на доске n×n можно расставить n не угрожающих друг другу ладей?
Заметим, что при расстановке более n ладей хотя бы на одной вертикали или горизонтали их окажется не менее двух. Таким образом, n есть наибольшее число ладей на доске n×n, не угрожающих друг другу. Одна из простейших расстановок заключается в расположении ладей вдоль главной диагонали доски (на полях a1, b2, c3, d4, e5, f6, g7, h8 для обычной доски)26.
Если ладьи занумерованы, то существует уже (n!)² различных расположений n ладей, не угрожающих друг другу. Это следует из того, что n подходящих полей можно выбрать n! способами и столько же способов имеется для расположения на этих полях n занумерованных ладей.
Итак, n рабочих можно назначить на n работ n! способами. Пусть теперь нужно сделать новое назначение, причем каждый рабочий хочет сменить свою предыдущую работу. Сколько существует таких назначений? В «ладейной» постановке эта задача формулируется так:
| An = n! | ( | 1 2! | — | 1 3! | + | 1 4! | — … + | (-1) n n! | ). |
| A8 = 8! | ( | 1 2! | — | 1 3! | + | 1 4! | — … + | 1 8! | ) = 14833, |
т. е. при дополнительном условии число расстановок восьми ладей, не угрожающих друг другу, уменьшается почти втрое.
Какое наибольшее число ладей можно расставить на доске 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 так, чтобы они держали под угрозой все поля доски?
