Комбинаторика

[Simba]

Может это просто, но я не понимаю в чём дело, 2 задачи:
1. В игре нарды 15 белых и 15 черных шашек стоят на 24 полях так, что каждое поле пустое или забито несколькими белыми шашками, или забито несколькими черными шашками. Сколькими способами можно так расставить?
2. 12 рыцарей сидят за круглом столом так, что каждый из них враждует с двумя соседними(и только с ними). Как выбрать 5 рыцарей так, чтобы выбранные оказались не враждующими?

Есть соображения по 2ой: мы выбираем 5 рыцарей, а значит не выбираем 7. Расставим этих невыбранных рыцарей по кругу так, чтобы между ними можно было поместить по рыцарю - образуется 7 таких мест, т.е. расставляя выбранных рыцарей в эти 7 мест мы можем гарантировать что они не будут враждовать, и так получается кол-во сочетаний из 7 по 5: 7!/5!*2!=21. (простите, не освоил ббкод) Но ответ 36. Что я не учел?

(Простите за мою местами математическую неграмотность, я общещаю научится это делать как следует, но думаю что моя идея вам понятна)

[caxap]

(Не уверен, но выскажусь)

1) Сначала нужно "разделить" поля: $k$ отдать чёрным, $j$ белым, $24-k-j$ будут пустыми. Затем разместить чёрные шашки на $k$ полях (без оставления пустых полей), белые -- на $j$. И просуммировать по всем возможным $k,j$.

[Alexey1]

В первой задаче используйте схему размещения неразличимых дробинок по ячейкам. В Вашем случае, дробинками являются шашки, а ячейками поля. Количество способов которыми можно разместить $n$ дробинок по $m$ ячейкам равно $C_{m+n-1}^n$ (дробинки могут попадать как в одну ячейку так и в разные).
Во второй задаче, если я правильно понял условие, выбирайте через одного.

[ewert]

Alexey1 в сообщении #358877 писал(а):

Во второй задаче, если я правильно понял условие, выбирайте через одного.

И тогда непонятно, почему 5, а не 6 -- это противоречит симметрии задачи. Да и при чём тут вообще комбинаторика.

[Alexey1]

ewert в сообщении #358879 писал(а):

И тогда непонятно, почему 5, а не 6 -- это противоречит симметрии задачи. Да и при чём тут вообще комбинаторика.

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

[Simba]

Цитата:

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

Нет. Вы считаете элементы неразличимыми, а их 2 вида: белые и черные.

Цитата:

Во второй задаче, если я правильно понял условие, выбирайте через одного.

Ну так к примеру: пронумеруем рыцарей 1,2,3,...,12. Через одного т.е. 1 3 5 ... 11 или 2 4 6 ... 12. Ну тогда 1 и 10 никогда не выстретятся! А ведь они не враждуют, а враждует только те, кто сидит рядом.

-- Пн окт 04, 2010 19:50:51 --

Alexey1 в сообщении #358881 писал(а):

ewert в сообщении #358879 писал(а):

И тогда непонятно, почему 5, а не 6 -- это противоречит симметрии задачи. Да и при чём тут вообще комбинаторика.

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

Так причем тут симметрия? Сдесь её не должно быть: враждуют ТОЛЬКО соседи.

[gris]

По второй задаче: между выбранными рыцарями сидит от одного до трёх невыбранных рыцарей. Каждая выборка определяется положением либо тройки подряд сидящих не выбранных - это 12 вариантов либо положением двух пар подряд сидящих невыбранных - это 96\4=24 варианта.

[Alexey1]

Simba в сообщении #359054 писал(а):

Нет. Вы считаете элементы неразличимыми, а их 2 вида: белые и черные.

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

Simba в сообщении #359054 писал(а):

Ну так к примеру: пронумеруем рыцарей 1,2,3,...,12. Через одного т.е. 1 3 5 ... 11 или 2 4 6 ... 12. Ну тогда 1 и 10 никогда не выстретятся! А ведь они не враждуют, а враждует только те, кто сидит рядом.

А почему они должны встретиться? Вы же написали

Simba в сообщении #358781 писал(а):

Как выбрать 5 рыцарей так, чтобы выбранные оказались не враждующими?

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

[deep blue]

Цитата:

А почему они должны встретиться?...
Да и при чём тут вообще комбинаторика...

Видимо речь во второй задаче о количестве всевзможных способов такого выбора. Тогда и рыцари должны будут встретиться в некоторых выборках и комбинаторика станет при чем. Насколько я помню похожие задачи (завязанные на соседях) решаются при помощи формулы включений-исключений, и тогда ответ не будет односложным, но это все на вскидку...
По первой задаче думаю так же как и сахар, но с небольшой поправкой: (слагаемые суммы надо дополнительно домножить на $C_{n}^kC_{n-k}^j$), то есть получится что-то типа $\sum\limits_{j=1}^{7}\sum\limits_{k=1}^{7} C_{n}^kC_{n-k}^jP(15,k)P(15,j)$
где $P(15,k)$ известная комбинаторная формула размещения 15 черных шашек на k полях, при чем леко ограничить снизу число шашек на каждом поле двойкой. Если я правильно понял, Alexey1 предлагает то же самое.

[Simba]

Alexey1 в сообщении #359074 писал(а):

Simba в сообщении #359054 писал(а):

Simba в сообщении #358781 писал(а):

Как выбрать 5 рыцарей так, чтобы выбранные оказались не враждующими?

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

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

[caxap]

deep blue в сообщении #359095 писал(а):

но с небольшой поправкой: (слагаемые суммы надо дополнительно домножить на $C_{n}^kC_{n-k}^j$

Я это и имел в виду, говоря про раздел полей. А почему вы суммируете до 7?

[deep blue]

Число ячеек, занимаемых черными фишками, не может быть более семи, ибо в каждой ячейке не менее двух фишек, которых всего 15. А так, в принципе, суммировать можно хоть до бесконечноси, очевидно это не повлияет на правильность.