Вопрос по математике

Royan · 21.03.2002, 18:06

Всем привет!
Тут возникла одна задачка, поетому если кто знает как ее решать или кто сможет ее решить огромная просьба, пожалуйста помогите
Условия:
Сколькими способами можно расположить N супружеских пар, так чтобы мужчины и женщины чередовались и никакаие двое супругов не сидели вместе.

Со всем уважением, Всего Royan!

Countach · 22.03.2002, 15:28

Не ну если я тебя правильно понял, то это из дет.сада проблемка
Расположить мона N! вариантами
N factorial

Darina · 22.03.2002, 15:46

А я так пояла, что они сидят в ряд или в круг(если М и Ж чередуются), получается, Ж 1-й пары нельзя сажать с М 2-й пары, если в следующей паре сидит Ж 2-пары. Значит, меньше, чем N!, а дальше я запуталась

Darina · 22.03.2002, 16:38

А может и не запуталась

Вероятнее всего бред, но:
for (i=0; i<=N-1; i++)
num=num+(N-2)**i; //** - типа возведение в степень
//num - результат
--------------------------------------
Ход мыслей (не смеяться, ежели чего

)
3 пары: вариант один Ж1М3Ж2М1Ж3М2
4 пары: Ж1(М3М4)Ж2(М1М2)Ж3(М1М2)Ж4(М2М3) - похоже на двоичную систему, кол-во вариантов 2**4-1=15
5 пар - то же, но типа 3-ная система ...
-------------
Хотя, бред скорее всего

забыла дискретную математику напрочь...

[subway]design · 22.03.2002, 16:48

Это ж комбинаторика, 10ый класс...

Если по кругу:

Преамбула:
1) n - четное, т.к. пары.
2) Жен - n/2, мужей столько же.

Считаем сколько способов есть посадить поочередно, м-ж-м-ж...:

(n/2)!*(n/2)!
(n/2)! - варианты рассадить мужчин

Потом смотрим на жен относительно мужей (феминистки, успокойтесь):

Вариантов посадить жену рядом с мужем два. Жен всего n/2, так что из полученного выражения надо вычесть (n/2)*2, умноженное на варианты рассадить мужей - (n/2)!:

(n/2)!*(n/2)!-(n/2)*2*(n/2)!

Целиком это выглядит так: (n/2)!*((n/2)!-(n/2)*2) Объяснить последнюю формулу можно так: (n/2)!-(n/2)*2 - это варианты рассадки жен относиттельно мужей, (n/2)! - варианты чередования, а (n/2)*2 - нахождение рядом с мужем. И умножается все это на варианты рассадки мужей - (n/2)!

ВНИМАНИЕ! Посмотрите не проврался ли я, находу придумывал.

Royan · 22.03.2002, 18:28

Я мозгами тоже немного пошевилил и попытался въехать в твою иде subway. мне почему то кажется что (N/2)! как-то по другому надо применять иначе по твоей формуле получиться что мужики могут сидеть рядом или жены (что по сути дела все равно нарушает условия) Моя идея:

(N)! - (N/2)*2 - D = результат
где D это число возможных рассадок жены рядом с женой или М рядом с М

и вот что на данный момент у нас есть точно

N/2 - число жен
N/2 - число мужей

(N/2)*2 - число возможных посадок одного супруга рядом с другим т.к. можно сесть либо справа либо слева

(N)! - число возможных рассадок всех.

[subway]design · 22.03.2002, 18:47

Смотри: если мужиков можно рассадить (n/2)! способами, а женщин тоже (n/2)! способами (это точно верно, нет смысла спорить), то вариантов рассадить (М через одного+Ж через одну) == (n/2)!*(n/2)! причем что-то вычитать не надо, т.к. если эту конструкцию повернуть на одно сидячее место, то НИЧЕГО не изменится - они ж по кругу сидят.

О! Теперь надо просто придумать варианты рассадить жен так, чтоб хоть одна с мужем сидела и (n/2)!*(n/2)! поделить на это число. Вот:

(n/2)!*(n/2)!/X

где X - это варианты рассадить жен рядом с мужем !! внутри конструкции м-ж-м-ж-м-ж !!

Сейчас еще подумаю...

[subway]design · 22.03.2002, 19:07

Я придумал:

m=n/2

Значит давай рассадим ВСЕХ жен рядом с мужьями: это один вариант. Остальные жены могут перемещаться (m-1)! способами, т.е. резмещений относительно одной жены == 1-(m-1)! а всего жен == m, следовательно X=(1-(m-1)!)*m, т.е. ответ:

m=n/2
(m)!*(m)!/(1-(m-1)!)*m

Всем спасибо, ответ правильный.

RFMitrio · 22.03.2002, 22:07

мдя-аааа....

Сбор математиков. Скажем наркотикам "иногда".

Цитата:

1) n - четное, т.к. пары.
2) Жен - n/2, мужей столько же.

Нет, я конечно понимаю, что в браке муж-половинка и жена - половинка. Но всетки не надо расчлененки и будем считать, что если пар N, то и жен и мужей - N.

Цитата:

Не ну если я тебя правильно понял, то это из дет.сада проблемка
Расположить мона N! вариантами
N factorial

no comments.
----
2Royan: На истинность в последней инстанции не претендую, но по-моему:
Kvar = n!*(n!-2)+сумма_по_i_от_2_до_n( (n-i)! )
Но то что здесь не одно слагаемое, а много - это 100%.

[subway]design · 23.03.2002, 09:06

Сорри, я считал, что n - это ВСЕ люди, а пар тогда - m=n/2.

По-моему, формулу (n)!*(n)!/((1-(n-1)!)*n) достаточно легко объяснить, а поэтому вроде бы она правильная..

В любом случае "сумма_по_i_от_2_до_n" не встречалась ни в одной известной мне задаче. Можешь объяснить с т.з. комбинаторики что это значит?