11:56 

Дилетант
На плечах гигантов, на спинах электронов
Помогите с детской задачей по комбинаторике ))
Точнее, по теории вероятностей, но дело всё же в комбинаторике.
Задача такая. Есть 10 человек, которые стоят в кругу. На 4 из них надеты белые перчатки, на 6 — черные.
Какова вероятность, что никакие два человека в белых перчатках не стоят вместе.

Формула классической вероятности `P(A)=m/n`.
И вот, проблемы уже начинаются с расчетом `n`.
Если считать просто "по формуле" перестановки с повторениями, то получаем всего перестановок таких людей: `{10!}/{4!*6!}`
И еще разделим на 10 из-за того, что они стоят в кругу. Имеем: `n={9!}/{4!*6!}`.
Я здесь не уверена до конца, что так можно...

В учебнике написан вот такой способ расчета `n`.
Ставим в круг 6 человек в черных перчатках (это можно сделать единственным способом: просто поставить). Расставляем в промежутки 4 человека в белых перчатках. Имеем: 6 способов для расстановки первого, 7 для второго, 8 для третьего, 9 для четвертого. И всё это разделим на 4!, так как они неразличимы.
Получим:
`n={6*7*8*9}/{4!}={9!}/{4!*5!}`
Т.е. с моим ответом не сходится.
Хорошо, но если мы сделаем наоборот: сперва расставим белых, потом черных?
Тогда имеем по той же логике:
`n={4*5*6*7*8*9}/{6!}={9!}/{3!*6!}`

Что я делаю не так?

@темы: Теория вероятностей, Комбинаторика

Комментарии
2018-07-26 в 13:32 

Trotil
Оба ответа неправильны, т.к. они не учитывают возможные дополнительные симметрии после вращения.

Давай попробуем решить задачу для
чёрных - 4, белых - 2.

2018-07-26 в 13:42 

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

Ну положим.
Черных 4, белых 2. Всего вариантов 3. ббчччч, бчбччч, бччбчч.

2018-07-26 в 13:44 

Дилетант
На плечах гигантов, на спинах электронов
Например, количество подходящих вариантов в исходной задаче 3, если я правильно посчитала. А в ответе 15.

2018-07-26 в 13:47 

Дилетант
На плечах гигантов, на спинах электронов
То есть, в указаниях прямо так и пишут.
Расставим 6 человек в черных перчатках. Количество мест для первого человека в белых перчатках - 6, для второго 5, для третьего 4, для четвертого 3. Поскольку люди неразличимы, делим это количество на 4!. Имеем:
6*5*3*4/4! = 15.
У меня руки опускаются от такой логики...

2018-07-26 в 13:53 

Trotil
Вариантов всего два, вместе ведь сажать нельзя.
Тут либо делать, как "по учебнику", или как правильно.

2018-07-26 в 14:05 

Дилетант
На плечах гигантов, на спинах электронов
Вариантов всего два, вместе ведь сажать нельзя.
Я пока только все варианты считаю.
А подходящих 2 из 3.

2018-07-26 в 14:24 

Trotil
Я тут написал программу (совсем необязательно, что правильно :D ), она выдала, что для n=6, m=4 есть только три верные расстановки:

0001010101
0010010101
0010100101

Похоже на правду. Или нет?

2018-07-26 в 14:28 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, да, верных три )))
Это я вчера руками посчитала. Это достаточно легко.
Мой способ:
8 человек из этих 10 расставляются однозначно - через одного. А потом считается, сколько разных вариантов вставить оставшихся двух черных. Первого черного - в любое место - 1 вариант. И еще одного - для него три разных.

2018-07-26 в 14:29 

Дилетант
На плечах гигантов, на спинах электронов
Но вот я думаю: нет ли формулы типа сочетания с повторениями, при которой этот ответ можно получить "чисто формально".
И как считать количество всех возможных расстановок.

2018-07-26 в 14:58 

Trotil
Я что-то забыл, что мы считаем вероятность, а не число расстановок белых и чёрных.
Это сильно меняет дело.

Для вероятности удобно считать каждого человека уникальным: 1 расстановка людей = 1 элементарный исход. Некоторые расстановки людей будут складываться в одну и ту же последовательность белых и чёрных, но это не страшно, это лишь будет означать, что некоторые расстановки возникают чаще других (что правда).

Зафиксируем одного (допустим, белого с номером 1) на первом месте, следовательно, остальных можно расставить 9! различными способами.

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

0001010101 6!*4!
0010010101 6!*4!
0010100101 6!*4!, циклическим сдвигом на 5 эта расстановка переходит сама в себя, но это учитывать не нужно (и делить на два тоже не надо).

Суммируем, делим одно на другое...

Можно не фиксировать порядок и точку отчёта, тогда это будет автоматом означать, что числитель и знаменатель нужно умножить на 10.

2018-07-26 в 15:04 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, ха!
То есть, изначально, моя формула для n была верна.
И для m тоже (с учетом 6!*4!)... :upset:
Что же делать с учебником? :(

2018-07-26 в 15:05 

Дилетант
На плечах гигантов, на спинах электронов
Спасибо!

2018-07-26 в 15:13 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, нет, еще один вопрос.
Так что же нам делать с симметриями вращения при расчете общего количества способов? Там ведь не все перестановки уникальны?..

2018-07-26 в 15:23 

Trotil
Предлагаю ничего не делать. Повторю, что существуют два подхода - учитывать симметрии вращения, но тогда получится, что одна комбинация, например, вида 1010101010 будет встречаться чаще, чем 1111100000. Это неудобно для вычисления вероятности. И второй подход, в котором симметрии не учитываются, и тогда все комбинации людей (а люди все разные!) будут равновероятны и это всё упрощает.

2018-07-26 в 16:11 

Ответ то какой?

URL
2018-07-26 в 16:14 

Дилетант
На плечах гигантов, на спинах электронов
3*6!*4!/9!

Trotil, ты так предлагаешь? Верно я мыслю?

2018-07-26 в 16:24 

А в учебнике?

URL
2018-07-26 в 16:28 

Trotil
Вероятно, да...

2018-07-26 в 17:49 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, Вероятно, да... :alles:
Спасибо ))

В учебнике ответ такой.
Всего способов расставить 4 белых, если черные уже стоят: 6*7*8*9/4!.
Подходящих способов расставить этих же 4 белых: 6*5*3*4/4!
Вероятность, соответственно, вычисляется как одно деленное на другое.
Кстати, очень стройное решение... :hmm:

2018-07-26 в 18:00 

Trotil
Кстати, это упрощается в дробь 1/7. А тестовая программа выдаёт примерно 1/8.4 Говнокод за 10 минут:

2018-07-26 в 18:04 

Trotil
Кстати, это упрощается в дробь 1/7. А тестовая программа выдаёт примерно 1/8.4.

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

Это печально. Ошибки пока не вижу, но она есть.

[mel@g4 Denis3]$ g++ -std=c++11 testperm.cpp -o testperm; ./testperm
count=1000000
count_2=119022
div=8.40181
[mel@g4 Denis3]$ g++ -std=c++11 testperm.cpp -o testperm; ./testperm
count=1000000
count_2=118410
div=8.42523
[mel@g4 Denis3]$ g++ -std=c++11 testperm.cpp -o testperm; ./testperm
count=1000000
count_2=119033
div=8.40103
[mel@g4 Denis3]$ g++ -std=c++11 testperm.cpp -o testperm; ./testperm
count=1000000
count_2=119020
div=8.39195
[mel@g4 Denis3]$ g++ -std=c++11 testperm.cpp -o testperm; ./testperm
count=1000000
count_2=118975
div=8.40513

2018-07-26 в 18:16 

Trotil
(6!*4! + 6!*4! + 6!*4!/2)/9! = 10/84.

Хм.

2018-07-26 в 18:19 

Trotil
> Всего способов расставить 4 белых, если черные уже стоят: 6*7*8*9/4!.
> Подходящих способов расставить этих же 4 белых: 6*5*3*4/4!
> Вероятность, соответственно, вычисляется как одно деленное на другое.
> Кстати, очень стройное решение... :hmm:

А если здесь поделить одно на другое, то тоже будет 10/84.
Пойду сдавать диплом.

Нет, я так не играю. Ошибка в программе? Правильный ответ - 1/7?

2018-07-26 в 18:37 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, вот тебе и детская задача ))

2018-07-26 в 18:37 

Дилетант
На плечах гигантов, на спинах электронов
Правильный ответ - 1/7?
Я спрошу.

2018-07-26 в 18:43 

Trotil
Дилетант, кого спросишь?
В учебнике ответ 10/84.

2018-07-26 в 18:47 

Дилетант
На плечах гигантов, на спинах электронов
Trotil, а, ну да...

2018-07-26 в 18:50 

Trotil
All_ex, приди и рассуди! =)

2018-07-26 в 19:23 

P(m m d m m d m d m d) = (6!*4!)/10!
P(m m d m d m m d m d) = (6!*4!)/10!
P(m m m d m d m d m d) = (6!*4!)/10!

С учётом поворотов и центральной симметрии во втором случае имеем (10+5+10)*(6!*4!)/10!.

URL
2018-07-26 в 22:35 

Trotil
Гость, вот так видно, что это правильный ответ.

2018-07-26 в 22:40 

Дилетант
На плечах гигантов, на спинах электронов
Большое спасибо всем откликнувшимся! :white:

2018-07-26 в 23:28 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Trotil, All_ex, приди и рассуди! =)
:alles: ...

кстати, а товарищи различаются как индивидуумы или только цветом перчаток?... :upset:

2018-07-26 в 23:34 

Дилетант
На плечах гигантов, на спинах электронов
All_ex, :bigkiss:
Товарищи должны различаться. Иначе задача уж сильно громоздкая получается... Так мне кажется. Хотя как бы нас это в итоге не должно волновать.

2018-07-26 в 23:47 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Если все индивидуумы, то можно рассуждать так...

Выберем одного в белых перчатках и разорвём круг...
остаётся 9 человек в линию - `n = 9!` вариантов...
чёрные перчатки - `6!` вариантов... между ними на пять мест ставим троих белых - `A_5^3 = 5*4*3` вариантов...
итого, `P = {5*4*3*6!}/{9!} = 5/{42}` ...

вроде ответ как у всех... :nope:

2018-07-27 в 00:05 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
прикинул для неразличимых... тоже 5/42 получилось...
:upset: ... мистика...

2018-07-27 в 10:57 

Дилетант
На плечах гигантов, на спинах электронов
All_ex, ... мистика...
:alles:

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная