2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 рассадка за круглым столом
Сообщение19.11.2008, 14:44 


20/09/08
6
Москва
Добрый день.

Проверьте пожалуйста, правильное ли мое решение?

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

Решение: Всего рассадок имеется (2n-1)!. Посчитаем вероятность дополнительного события - что на пары разбить нельзя. Разбить на пары нельзя, если есть 3 мужчины сидящих рядом. Следовательно, число рассадок, при которых на пары разбить нельзя равно $$\frac{C_{n}^{3}\cdot 3! \cdot (2n-3)!}{2n \cdot ((2n-1)!)}$$. Т.е. сначала мы выбираем 3 мужчин, потом упорядочиваем их как хотим, потом упорядочиваем как угодно остальных, и делим на 2n - т.к. стол круглый.

Я не уверен, что это решение правильное.

 Профиль  
                  
 
 
Сообщение19.11.2008, 14:57 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
$MMFMMFFMFF$ - разбейте на пары.

 Профиль  
                  
 
 
Сообщение19.11.2008, 15:01 
Заслуженный участник


11/05/08
32166
Не годится. Во-первых, Вы не учли, что эта тройка мужиков может оказаться в любом месте. Во-вторых (более принципиально), Ваши варианты не являются взаимоисключающими.

На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...). Эти два класса тоже пересекаются, но уже по легко отслеживаемым комбинациям: тем и только тем, в которых мужчины и женщины чередуются.

 Профиль  
                  
 
 Re: рассадка за круглым столом
Сообщение19.11.2008, 15:06 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Покоритель курумника писал(а):
Я не уверен, что это решение правильное.

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

Вместо этого посчитайте: 1) количество способов разбить мужчин и женщин по парам 2) количество способов разместить эти пары в кольцо 3) количество способов решить в каждой паре, сидит ли мужчина левее женщины или правее
Но это решение не совсем правильно, потому что какие-то рассадки мы посчитали дважды. Это именно те рассадки, когда разбить на пары можно не единственным способом (двумя способами). Это очень легко посчитать -- в конце надо это число отнять от того, что получилось после пункта 3.

Добавлено спустя 1 минуту 59 секунд:

ewert писал(а):
На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...).

Я думаю, что речь шла о циклических рассадках. То есть две рассадки, отличающиеся поворотом, совпадают. Поэтому это один и тот же класс.

 Профиль  
                  
 
 
Сообщение19.11.2008, 15:09 
Заслуженный участник


11/05/08
32166
Хорхе в сообщении #159868 писал(а):
Я думаю, что речь шла о циклических рассадках. То есть две рассадки, отличающиеся поворотом, совпадают. Поэтому это один и тот же класс.

Это не имеет значения. Речь о вероятности, поэтому повороты можно как учитывать, так и нет -- смотря что удобнее. Удобнее учитывать (т.е. считать расстановки, совпадающие после поворота, различными).

 Профиль  
                  
 
 
Сообщение19.11.2008, 15:41 
Заслуженный участник
Аватара пользователя


14/02/07
2648
ewert писал(а):
Это не имеет значения. Речь о вероятности, поэтому повороты можно как учитывать, так и нет -- смотря что удобнее. Удобнее учитывать (т.е. считать расстановки, совпадающие после поворота, различными).

Вы правы. Я почему-то решил, что задача посчитать количество способов, а не вероятность :)

 Профиль  
                  
 
 
Сообщение19.11.2008, 16:17 


20/09/08
6
Москва
Большое спасибо за ответы, TOTAL, ewert и Хорхе.

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

На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...). Эти два класса тоже пересекаются, но уже по легко отслеживаемым комбинациям: тем и только тем, в которых мужчины и женщины чередуются.


Правильно ли я понимаю, что число вариантов в четном и в нечетном случае по $$2^{n} \cdot (n!)^{2}$$, в случае пересечения 2\cdot (n!)^{2} и ответ
$$\frac{2^{n+1} \cdot (n!)^{2} - 2(n!)^{2}}{(2n)!}$$?

 Профиль  
                  
 
 
Сообщение19.11.2008, 16:19 
Заслуженный участник


11/05/08
32166
Да (если я чего не зевнул).

 Профиль  
                  
 
 
Сообщение19.11.2008, 16:21 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Очень похоже на правду.

 Профиль  
                  
 
 
Сообщение19.11.2008, 16:22 


20/09/08
6
Москва
ewert писал(а):
Да (если я чего не зевнул).


По крайней мере для n=1,2 это верно, т.к. вероятность равна 1.

Еще раз спасибо.

 Профиль  
                  
 
 Re: рассадка за круглым столом
Сообщение20.10.2014, 10:20 


29/04/14
139
Также очень благодарю всех отвечавших, очень хорошее пояснение.
Мне вот непонятно только одно - почему ответ действительно оказывается правильным, несмотря на то, что мы учитываем случаи циклического сдвига как разные рассадки? То есть учитываем количество этих случаев как в числителе, так и знаменателе.
Есть какой то строгий способ доказать, что такая операция правомерна?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group