[Дилетант]

Помогите с детской задачей по комбинаторике ))
Точнее, по теории вероятностей, но дело всё же в комбинаторике.
Задача такая. Есть 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!}`

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

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

Comments

[Trotil]

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

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

[Дилетант]

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

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

[Дилетант]

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

[Дилетант]

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

[Trotil]

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

[Дилетант]

Вариантов всего два, вместе ведь сажать нельзя.

Я пока только все варианты считаю.
А подходящих 2 из 3.

[Trotil]

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

0001010101
0010010101
0010100101

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

[Дилетант]

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

[Дилетант]

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

[Trotil]

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

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

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

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

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

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

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

[Дилетант]

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

[Дилетант]

Спасибо!

[Дилетант]

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

[Trotil]

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

[Гость]

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

[Дилетант]

3*6!*4!/9!

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

[Гость]

А в учебнике?

[Trotil]

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

[Дилетант]

Trotil,

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

Спасибо ))

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

[Trotil]

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

int main()
{
	int a1=0;
	int a2=0;
	int a3=0;
	int a4=0;
	int temp,count=0, count_2=0;
	
    std::srand(unsigned(std::time(0)));
//    int random_variable = std::rand();
	
	for (int j=0; j<1000000; j++)
	{
		a1=0;
		a2=0;
		a3=0;
		a4=0;
		
		
		
		do
	{
		temp = 1 + std::rand() % 10 ;
	//	cout << temp << endl;
		if (!a1)
		{
			a1 = temp;
			continue;
		}
		if (!a2)
		{
			if (temp != a1) {a2 = temp;}
			continue;			
		}
		if (!a3)
		{
			if ((temp != a1) && (temp != a2)) {a3 = temp;}
			continue;			
		}
		if (!a4)
		{
			if ((temp != a1) && (temp != a2) && (temp != a3)) {a4 = temp;}
			continue;			
		}
		
	} while (!a4);
	
	
	if ( (abs(a1-a2) == 1) || (abs(a1-a3) == 1) || (abs(a1-a4) == 1) || (abs(a2-a3) == 1) || (abs(a2-a4) == 1) || (abs(a3-a4) == 1)) 
	 { 
// cout << "A" << a1 << " " << a2 << " " << a3 << " " << a4 << endl; 
	count_2++;}
	else
	if (( (a1 == 1) || (a2 == 1) || (a3 == 1) || (a4 == 1)) && ( (a1 == 10) || (a2 == 10) || (a3 == 10) || (a4 == 10))) 
	{
	//	cout << "Q" << a1 << " " << a2 << " " << a3 << " " << a4 << endl;
count_2++;}
	
	count++;
	}
	
	cout << "count=" << count << endl;
	cout << "count_2=" << count - count_2 << endl;
	cout << "div=" << (double)count/(count-count_2) << endl;
	
	return 0;
}

[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

[Trotil]

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

Хм.

[Trotil]

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

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

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

[Дилетант]

Trotil, вот тебе и детская задача ))

[Дилетант]

Правильный ответ - 1/7?

Я спрошу.

[Trotil]

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

[Дилетант]

Trotil, а, ну да...

[Trotil]

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

[Гость]

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!.

[Trotil]

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