Разбойники

[Asker Tasker]

Задача, наверное, очень старая, но хочется проверить своё решение.
"Двенадцать разбойников сидят вокруг костра и каждый ненавидит двух своих ближайших соседей. Сколькими способами можно выбрать пятерых разбойников так, чтобы они не ненавидели друг друга? Какова вероятность, что наугад выбранная пятёрка будет "мирной"?"

Обозначим произвольного разбойника единицей и будем условно считать его "первым", тогда он ненавидит своих соседей - "второго" и "двенадцатого". Обозначим их нулями. "Второй" разбойник ненавидит первого и.. третьего - его тоже обозначим единицей - и так размышляя получим следующий набор:
1-0-1-0-1-0-1-0-1-0-1-0

Таким образом наше множество разбилось на два непересекающихся подмножества нулей и единиц, а событие $А := $"выбраны пять разбойников, не ненавидящих друг друга" на два несовместных события "выбраны пять нулей" и "выбраны пять единиц", то есть число способов выбрать "мирную пятёрку" равно:
$N \left( A \right) = C_{6}^{5} + C_{6}^{5} = 2 \cdot 6 = 12$

Если же выбираются пятеро разбойников произвольно, то всего способов это сделать $C_{12}^{5}$, а значит вероятность выбрать "мирную пятёрку" равна $\frac{12}{C_{12}^{5}}$

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

[chessar]

А если например выбрать "4 нуля" и "1 единицу", так чтобы эта "единица" ненавидела оставшиеся 2 "нуля"?

[Shtorm]

chessar в сообщении #616795 писал(а):

А если например выбрать "4 нуля" и "1 единицу", так чтобы эта "единица" ненавидела оставшиеся 2 "нуля"?

И соответственно, по аналогии "4 единицы" и "1 нуль", так же.

[Asker Tasker]

Ой-ой. И как это учесть? :(
Выбрать единицу можно шестью способами. Тогда "откидываются" два нуля, остальные четыре входят в пятёрку.
То есть ещё шесть вариантов. С одним нулём - та же история. То есть всего добавляем двенадцать способов выбрать пятёрку.

Но тогда можно выбрать и две единицы с тремя нулями. Если между ними есть ещё хоть одна единица, то "отбросится" четыре нуля и останется два нуля и четыре единицы, то есть в этом случае три нуля выбрать не получится. Зато если мы выберем две единицы, отделённые друг от друга лишь одним смежным с ними нулём, то тогда "отбросятся" лишь три нуля: 0-1-0-1-0, а останется ещё три - и мы тоже сможем сформировать пятёрку. Выбрать две подряд идущие единицы из шести, расположенных в круге, можно столькими способами, сколькими можно выбрать первую единицу, то есть шестью. Таким образом наборы (два нуля, три единицы) и (три единицы, два нуля) добавляют ещё 12 вариантов.

Итого $12 + 12 + 12 = 36$ вариантов. Верно?

А более красивого (или хотя бы более короткого) варианта решения нет? Может, есть какой-то общий способ решения этой или подобных задач?

[chessar]

Asker Tasker,
Вы попробуйте прежде посчитать сколькими способами можно выбрать 5 разбойников, среди которых как минимум двое ненавидят друг друга.

[Asker Tasker]

Ну, насколько я понимаю, N("выбрать пятёрку, в которой как минимум двое ненавидят друг друга") $=$ N("выбрать пятёрку") - N("выбрать пятёрку, в которой разбойники не ненавидят друг друга, т.е. никакие два не ненавидят") $= C_{12}^{5} - 36$?

Я хочу вывести ответ в виде общей формулы. Как, например, в такой задаче: есть $L$ различных львов и $T < L$ различных тигра. Нужно вывести их на арену так, чтобы никакие два тигра не шли друг за другом. Сначала считаем общее число способов расположить тигров между львами:
__Л__Л__Л__Л__Л__
На любом из пропусков может стоzть тигр, а число пропусков равно $L + 1$, поэтому соответствующее число расположений равно $C_{L + 1}^{T}$. Но в условии акцентировано внимание на том, что звери различные, поэтому полученное число нужно умножить на количество способов, которыми можно зверей одного вида "переставить" друг с другом - и получаем ответ в виде общей формулы: $N = C_{L+1}^{T} \cdot L! \cdot T! $

Я бы хотел сделать что-то подобное для задачи с разбойниками.

[chessar]

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

Рассуждения для доказательство этого примерно такие. Возьмём какого-нибудь разбойника (назовём его главным) и зафиксируем этот выбор. Далее все выбираемые комбинации разбойников распадаются на два класса - в одних из них участвует главный, а в других - нет. Для каждого класса посчитаем количество нужных нам комбинаций и сложим их. Для 1-го класса мы можем выбирать остальных $k-1$ разбойников среди оставшихся $n-3$ (мы сразу исключили еще и соседей главного, т.к. они не должны попасть в выборку). Для 2-го класса нам необходимо выбирать $k$ из $n-1$ разбойников (т.к. главный уже исключён, то его соседей мы уже не можем исключать). Но в каждой из полученных подзадач разбойники уже не сидят по кругу, а сидят в ряд и только крайние ненавидят по одному своему соседу. Т.е. необходимо найти число способов выбрать $\ell$ разбойников из $m$ сидящих в ряд и ненавидящих своих ближайших соседей (у каждого кроме крайних по два соседа, у крайних - по одному), так чтобы в это число не попали никакие два ненавидящих друг друга. Эта задача очевидно равносильна следующей:

Сколькими способами можно расставить $m-\ell$ нулей и $\ell$ единиц так, чтобы никакие две единицы не стояли рядом?
Решение этой задачи: $C_{m-\ell+1}^{\ell}$ способами.

В итоге, для 1-го класса мы имеем $\ell=k-1$, $m=n-3$ и число способов равно:
$C_{(n-3)-(k-1)+1}^{k-1}=C_{n-k-1}^{k-1}$.
Для 2-го класса $\ell=k$, $m=n-1$ и число способов равно:
$C_{(n-1)-k+1}^k=C_{n-k}^k$.

Ну я думаю для подзадачи про нули и единицы Вы разберётесь с решением.

(Оффтоп)

chessar в сообщении #616828 писал(а):

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

За это моё замечаение извиняюсь. К такому типу задач этот подход не применим. Я сначало тоже не верно рассуждал.