Определить количество расстановок ладей на шахматной доске

@_qikert · Регистрация: 16.11.2019

Author24 — интернет-сервис помощи студентам

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

Байт · 10.02.2020, 21:56

=8⁸

Добавлено через 1 минуту
Нет, я не прав. Погорячился. Подумать надо.

Добавлено через 6 минут
Похоже, что так: 2*8⁸ - 8!
Но уверенности нет...

@jogano · 10.02.2020, 22:10

8! - 8 ладей должны стоять так, чтобы попарно не бить друг друга. Каждая ладья занимает какою-то строку и какой-то столбец. Если строки перебирать по очереди 1-2-...-8, то для 1й строки можно поставить ладью в любой из 8-и столбцов, ладью во 2й строке - в любой из оставшихся 7-и столбцов и так далее.

Если придираться к условию, то ТС-у следовал бы оговорить, что ладей должно быть минимальное количество, а то так можно в каждую клетку поставить по ладье и каждая клетка будет бита, а это один способ.

Сообщение от Байт

=8⁸

Если нет условия на то, что ладьи не должны бить друг друга и их минимальное количество, то да. Это уже вопрос к ТС-у, который даёт размытое условие.

Байт · 10.02.2020, 23:07

Сообщение от jogano

размытое условие.

Да, есть такое дело. И я его, грешным делом, дополнил (для себя), что ладей должно быть 8. Ибо меньше не получится. Но ответ 8⁸ неверен, потому как учитывает расстановку всех по одной горизонтали, но не учитывает ту же вертикальную расстановку. Короче, "включения-исключения" в деле. Но вот как-то уверенности нет....

@angor6 · 10.02.2020, 23:08

Сообщение от Байт

Похоже, что так: $https://www.cyberforum.ru/cgi-bin/latex.cgi?2*8^8 - 8!$

Если мне память не изменяет и я правильно понимаю сформулированную задачу, то ответ именно таков. Конечно, если принять, что количество ладей минимально для контроля над всеми полями шахматной доски.

Байт · 10.02.2020, 23:15

Сообщение от angor6

то ответ именно таков.

Память, не память, но интуиция подсказывает такой ответ.
Ход рассуждений. Посчитаем конфигурации, когда на каждой горизонтали одна ладья. Потом те, где по ладье на каждой вертикали. Случай не бьющихся ладей мы посчитали дважды. Но "не аккуратненько как-то"

@angor6 · 10.02.2020, 23:36

К сожалению, я ошибся. Упомянутый мной ответ относится к следующей задаче: "Сколькими способами можно расставить 8 ладей, которые не могли бы бить друг друга, на доске размера 8×8?" Однако, поскольку в данном случае нет указания, что ладьи не должны бить друг друга, то их можно расставить и в один ряд. Поэтому количество вариантов расстановки увеличивается.

Байт · 10.02.2020, 23:40

Сообщение от angor6

количество вариантов расстановки увеличивается.

Энто-то ясно. Но вот насколько?

@angor6 · 11.02.2020, 00:09

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

@_qikert · 11.02.2020, 08:54 **[ТС]**

Какое кол-во вариантов поставить ладей на шахматную доску, так что бы они били все свободные клетки доски(ладьи могут бить друг-друга)
Напишите подробное решение)

@kabenyuk · 11.02.2020, 10:38

Сообщение от _qikert

бить друг-друга

Если нет условия на количество ладей, то придется делать так.
Ясно, что на доске должно быть не менее 8 ладей (8 горизонталей должны пробиваться). Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.). Оставшиеся 56 полей можно заполнить ладьями 2⁵⁶ способами (поле занято или нет). Итого получается
8!*2⁵⁶.
Если я нигде не ошибся, это и есть ответ.

Сообщение от _qikert

свободные поля?

Вот тебе раз - клон нашелся. Смотрим и мой вариант здесь
у меня получилось 8!*2⁵⁶

Добавлено через 28 минут
Нет, таки ошибся. Некоторые варианты подсчитаны дважды и даже больше.

Байт · 11.02.2020, 11:15

Сообщение от kabenyuk

Некоторые варианты подсчитаны дважды и даже больше.

А некоторые не подсчитаны вообще. Например, 8 ладей с линию.

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

@kabenyuk · 11.02.2020, 12:59

Сообщение от Байт

Например, 8 ладей с линию.

Нет, все подсчитано, только толку от этого никакого. Н-да, коварная оказалась задача.

Байт · 11.02.2020, 15:09

Сообщение от kabenyuk

Нет, все подсчитано,

Простите, не увидел.

Сообщение от kabenyuk

Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.).

Вот тут-то и пропущен вариант "8 в линию" Как и многие другие. Типа
a1 b1 c2 d2 e3 f3 g2 h1

Добавлено через 19 минут
Все-таки я склоняюсь к ответу 8*(2²² - 7!)

@angor6 · 11.02.2020, 15:14

Я предполагаю следующее:
1) минимальное количество ладей, которое нужно расставить на обычной шахматной доске, чтобы они контролировали все поля, равно восьми;
2) восемь ладей контролируют все поля шахматной доски, если
а) они расставлены по одной на каждой из восьми горизонталей (это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8$ способами, причём на одной вертикали может стоять и больше одной ладьи;
б) они расставлены по одной на каждой из восьми вертикалей (это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8$ способами, причём на одной горизонтали может стоять и больше одной ладьи.

Среди указанных выше способов дважды учтены расстановки, при которых на каждой горизонтали и каждой вертикали стоит по одной ладье. Количество таких расстановок равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?(8!)^2{.}$ В самом деле первую ладью можно поставить на любое из $https://www.cyberforum.ru/cgi-bin/latex.cgi?64$ полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из $https://www.cyberforum.ru/cgi-bin/latex.cgi?49$ полей, на которые можно поставить вторую ладью, и т. д. Значит, рассматриваемых расстановок существует $https://www.cyberforum.ru/cgi-bin/latex.cgi?64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4 \cdot 1=(8!)^2{.}$

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

Следовательно, существует $https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 8^8-(8!)^2$ способов, которыми можно расставить на обычной шахматной доске восемь ладей так, чтобы они контролировали все поля.

Байт · 11.02.2020, 15:38

Сообщение от angor6

В самом деле первую ладью можно поставить на любое из 64 полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из 49

Посмотрите внимательнее на свои рассуждения. Мне кажется, там ошибка. Одну и ту же расстановку считаете много раз.
У вас расстановки a1 b2 и b2 a1 считаются за разные.
Чтобы проверить себя, можно потренироваться на доске 3 х 3

Добавлено через 7 минут

Сообщение от angor6

2) восемь ладей контролируют все поля шахматной доски, если

А вот этот пункт совершенно верен. И именно его мне не хватало! Спасибо!

@angor6 · 11.02.2020, 15:40

Байт,

Не по теме:

нет, тренироваться я не стану: возраст уже не тот. Нужно смириться с тем, что комбинаторные задачи относятся к числу недостижимых для меня высот. :)

Спасибо за указание на ошибку!

Байт · 11.02.2020, 15:42

angor6,

Сообщение от Байт

на доске 3 х 3

Даже на доске 2 х 2 можно убедиться. Ваши рассуждения дадут 4. А в самом деле - 6

iifat · 11.02.2020, 15:44

Закину таки ещё вариант.
Разобьём варианты расстановки на три непересекающихся класса:
— присутствуют пустые вертикали (в каждой горизонтали кто-нить да стоит);
— присутствуют пустые горизонтали (в каждой вертикали...);
— нет ни пустых вертикалей, ни горизонталей.
Вариант 1, по формуле включений-исключений $https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=\sum\limits_{k=1}^7(-1)^{k-1}C_8^k8^{8-k}$
Поскольку $https://www.cyberforum.ru/cgi-bin/latex.cgi?(8-1)^8=\sum\limits_{k=0}^8(-1)^{k-1}C_8^k8^{8-k}$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=1+8^8-7^8$ .
Дальше — удвоить и добавить $https://www.cyberforum.ru/cgi-bin/latex.cgi?8!$ (это я не ору, это факториал).
Или я не Винни-Пух. А я — он, значит, всё в порядке.
Или всё же не он?

Байт · 11.02.2020, 15:52

Не по теме:

Сообщение от angor6

возраст уже не тот

Да ну? Готов поспорить, что я на пару годков постарше! Давайте так. Каждый год - кружка пива. Идет?:D

Добавлено через 7 минут

Сообщение от iifat

это я не ору, это факториал

Да и никто не орет.

Это нам еще поперло, что факториалы не двойные...
А по делу. N₁ - это ответ? ... Не, кажись ответ 2N₁ + 8! , да?
Но чегой-то сложно получается. И не похоже.
А чем вас мой ответ не устраивает?

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 919 Регистрация: 19.11.2012 Сообщений: 6,196
	11.02.2020, 12:59	13
	Сообщение от Байт Например, 8 ладей с линию. Нет, все подсчитано, только толку от этого никакого. Н-да, коварная оказалась задача. 0

@angor6 Любитель математики 1478 / 989 / 282 Регистрация: 27.01.2014 Сообщений: 3,280
	11.02.2020, 15:40	17
	Байт, Не по теме: нет, тренироваться я не стану: возраст уже не тот. Нужно смириться с тем, что комбинаторные задачи относятся к числу недостижимых для меня высот. :) Спасибо за указание на ошибку! 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 15:42	18
	angor6, Сообщение от Байт на доске 3 х 3 Даже на доске 2 х 2 можно убедиться. Ваши рассуждения дадут 4. А в самом деле - 6 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
		1
	Определить количество расстановок ладей на шахматной доске 10.02.2020, 20:16. Показов 11241. Ответов 27 Метки нет (Все метки) какое кол-во способ расставить ладей на шахматную доску, так чтобы они били все свободные поля? 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	10.02.2020, 21:56	2
	=8⁸ Добавлено через 1 минуту Нет, я не прав. Погорячился. Подумать надо. Добавлено через 6 минут Похоже, что так: 2*8⁸ - 8! Но уверенности нет... 1

@jogano $Эксперт по математике/физике$ 6358 / 4065 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	10.02.2020, 22:10	3
	8! - 8 ладей должны стоять так, чтобы попарно не бить друг друга. Каждая ладья занимает какою-то строку и какой-то столбец. Если строки перебирать по очереди 1-2-...-8, то для 1й строки можно поставить ладью в любой из 8-и столбцов, ладью во 2й строке - в любой из оставшихся 7-и столбцов и так далее. Если придираться к условию, то ТС-у следовал бы оговорить, что ладей должно быть минимальное количество, а то так можно в каждую клетку поставить по ладье и каждая клетка будет бита, а это один способ. Сообщение от Байт =8⁸ Если нет условия на то, что ладьи не должны бить друг друга и их минимальное количество, то да. Это уже вопрос к ТС-у, который даёт размытое условие. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	10.02.2020, 23:07	4
	Сообщение от jogano размытое условие. Да, есть такое дело. И я его, грешным делом, дополнил (для себя), что ладей должно быть 8. Ибо меньше не получится. Но ответ 8⁸ неверен, потому как учитывает расстановку всех по одной горизонтали, но не учитывает ту же вертикальную расстановку. Короче, "включения-исключения" в деле. Но вот как-то уверенности нет.... 0

@angor6 Любитель математики 1478 / 989 / 282 Регистрация: 27.01.2014 Сообщений: 3,280
	10.02.2020, 23:08	5
	Сообщение от Байт Похоже, что так: $https://www.cyberforum.ru/cgi-bin/latex.cgi?2*8^8 - 8!$ Если мне память не изменяет и я правильно понимаю сформулированную задачу, то ответ именно таков. Конечно, если принять, что количество ладей минимально для контроля над всеми полями шахматной доски. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	10.02.2020, 23:15	6
	Сообщение от angor6 то ответ именно таков. Память, не память, но интуиция подсказывает такой ответ. Ход рассуждений. Посчитаем конфигурации, когда на каждой горизонтали одна ладья. Потом те, где по ладье на каждой вертикали. Случай не бьющихся ладей мы посчитали дважды. Но "не аккуратненько как-то" 0

@angor6 Любитель математики 1478 / 989 / 282 Регистрация: 27.01.2014 Сообщений: 3,280
	10.02.2020, 23:36	7
	К сожалению, я ошибся. Упомянутый мной ответ относится к следующей задаче: "Сколькими способами можно расставить 8 ладей, которые не могли бы бить друг друга, на доске размера 8×8?" Однако, поскольку в данном случае нет указания, что ладьи не должны бить друг друга, то их можно расставить и в один ряд. Поэтому количество вариантов расстановки увеличивается. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	10.02.2020, 23:40	8
	Сообщение от angor6 количество вариантов расстановки увеличивается. Энто-то ясно. Но вот насколько? 0

@angor6 Любитель математики 1478 / 989 / 282 Регистрация: 27.01.2014 Сообщений: 3,280
	11.02.2020, 00:09	9
	Байт, наверное, нужно дождаться более точной формулировки задачи от автора вопроса, чтобы избавиться от неопределённости, указанной в сообщениях выше. 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	11.02.2020, 08:54 [ТС]	10
	Какое кол-во вариантов поставить ладей на шахматную доску, так что бы они били все свободные клетки доски(ладьи могут бить друг-друга) Напишите подробное решение) 0

	11.02.2020, 15:52

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 919 Регистрация: 19.11.2012 Сообщений: 6,196
	11.02.2020, 10:38	11
	Сообщение от _qikert бить друг-друга Если нет условия на количество ладей, то придется делать так. Ясно, что на доске должно быть не менее 8 ладей (8 горизонталей должны пробиваться). Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.). Оставшиеся 56 полей можно заполнить ладьями 2⁵⁶ способами (поле занято или нет). Итого получается 8!2⁵⁶. Если я нигде не ошибся, это и есть ответ. Сообщение от _qikert* свободные поля? Вот тебе раз - клон нашелся. Смотрим и мой вариант здесь у меня получилось 8!2⁵⁶ Добавлено через 28 минут* Нет, таки ошибся. Некоторые варианты подсчитаны дважды и даже больше. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 11:15	12
	Сообщение от kabenyuk Некоторые варианты подсчитаны дважды и даже больше. А некоторые не подсчитаны вообще. Например, 8 ладей с линию. Добавлено через 1 минуту А по поводу формулировки... Давайте ограничимся 8-ю ладьями, ибо при большем их количестве как-то в звдачке мало смысла... 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 15:09	14
	Сообщение от kabenyuk Нет, все подсчитано, Простите, не увидел. Сообщение от kabenyuk Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.). Вот тут-то и пропущен вариант "8 в линию" Как и многие другие. Типа a1 b1 c2 d2 e3 f3 g2 h1 Добавлено через 19 минут Все-таки я склоняюсь к ответу 8*(2²² - 7!) 0

@angor6 Любитель математики 1478 / 989 / 282 Регистрация: 27.01.2014 Сообщений: 3,280
	11.02.2020, 15:14	15
	Я предполагаю следующее: 1) минимальное количество ладей, которое нужно расставить на обычной шахматной доске, чтобы они контролировали все поля, равно восьми; 2) восемь ладей контролируют все поля шахматной доски, если а) они расставлены по одной на каждой из восьми горизонталей (это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8$ способами, причём на одной вертикали может стоять и больше одной ладьи; б) они расставлены по одной на каждой из восьми вертикалей (это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8$ способами, причём на одной горизонтали может стоять и больше одной ладьи. Среди указанных выше способов дважды учтены расстановки, при которых на каждой горизонтали и каждой вертикали стоит по одной ладье. Количество таких расстановок равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?(8!)^2{.}$ В самом деле первую ладью можно поставить на любое из $https://www.cyberforum.ru/cgi-bin/latex.cgi?64$ полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из $https://www.cyberforum.ru/cgi-bin/latex.cgi?49$ полей, на которые можно поставить вторую ладью, и т. д. Значит, рассматриваемых расстановок существует $https://www.cyberforum.ru/cgi-bin/latex.cgi?64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4 \cdot 1=(8!)^2{.}$ Если расставить восемь ладей так, чтобы хотя бы на одной горизонталям и хотя бы на одной вертикали было больше чем одна ладья, то не все поля шахматной доски будут под контролем. Следовательно, существует $https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 8^8-(8!)^2$ способов, которыми можно расставить на обычной шахматной доске восемь ладей так, чтобы они контролировали все поля. 1

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 15:38	16
	Сообщение от angor6 В самом деле первую ладью можно поставить на любое из 64 полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из 49 Посмотрите внимательнее на свои рассуждения. Мне кажется, там ошибка. Одну и ту же расстановку считаете много раз. У вас расстановки a1 b2 и b2 a1 считаются за разные. Чтобы проверить себя, можно потренироваться на доске 3 х 3 Добавлено через 7 минут Сообщение от angor6 2) восемь ладей контролируют все поля шахматной доски, если А вот этот пункт совершенно верен. И именно его мне не хватало! Спасибо! 1

iifat 2734 / 1814 / 199 Регистрация: 05.06.2011 Сообщений: 5,239
	11.02.2020, 15:44	19
	Закину таки ещё вариант. Разобьём варианты расстановки на три непересекающихся класса: — присутствуют пустые вертикали (в каждой горизонтали кто-нить да стоит); — присутствуют пустые горизонтали (в каждой вертикали...); — нет ни пустых вертикалей, ни горизонталей. Вариант 1, по формуле включений-исключений $https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=\sum\limits_{k=1}^7(-1)^{k-1}C_8^k8^{8-k}$ Поскольку $https://www.cyberforum.ru/cgi-bin/latex.cgi?(8-1)^8=\sum\limits_{k=0}^8(-1)^{k-1}C_8^k8^{8-k}$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=1+8^8-7^8$ . Дальше — удвоить и добавить $https://www.cyberforum.ru/cgi-bin/latex.cgi?8!$ (это я не ору, это факториал). Или я не Винни-Пух. А я — он, значит, всё в порядке. Или всё же не он? 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 15:52	20
	Не по теме: Сообщение от angor6 возраст уже не тот Да ну? Готов поспорить, что я на пару годков постарше! Давайте так. Каждый год - кружка пива. Идет?:D Добавлено через 7 минут Сообщение от iifat это я не ору, это факториал Да и никто не орет. Это нам еще поперло, что факториалы не двойные... А по делу. N₁ - это ответ? ... Не, кажись ответ 2N₁ + 8! , да? Но чегой-то сложно получается. И не похоже. А чем вас мой ответ не устраивает? 0