Представим, что вы организуете круглый стол, и вам важно, в каком порядке будут рассажены участники. В комбинаторике такую задачу называют «задачей о супружеских парах» или методом Le Problème des Ménages.
В этом уроке разберем, как работает такой метод.
Решаем задачу о супружеских парах
Для начала рассмотрим самую распространенную формулировку этой задачи:
Допустим, у нас есть
пар, каждая из которых состоит из мужчины и женщины.
Их нужно рассадить за круглым столом так, чтобы мужчины и женщины чередовались. При этом женщины должны сидеть на нечетных местах и ни одна из них не может сидеть рядом со своим партнером.
Нужно вычислить, сколько существует вариантов рассадки.
Чтобы решить эту задачу, используем принцип включения и исключения.
Для начала переведем задачу на язык математики и присвоим имена:
-
Пусть — множество пар
-
При этом — множество рассадок, в которых женщины занимают нечетные места
-
Нужно найти те члены в , для которых ни одна пара не сидит вместе
-
Выражение обозначим через множество расстановок
-
Множество обозначает пары из множества , которые нарушают правило
-
По симметрии размер зависит от размера , а не от конкретного выбора пар
-
Поэтому сделаем такой вывод — если , обозначим
Далее находим нужное число. Для этого применим принцип включения и исключения:
Далее введем обозначение — это количество способов, с помощью которых можно выбрать пар стульев, расположенных рядом друг с другом.
Наши плохих пар могут располагаться над плохими парами мест способами. Поэтому мы приходим к такому выражению:
После этого мы можем рассадить оставшихся женщин способами, а оставшихся мужчин — способами.
Вот так может выглядеть схема рассадки:
Здесь три пары сидят вместе, что не соответствует первоначальному условию рассадки.
Остается определить . Для этого разорвем окружность в фиксированной точке. Далее сотрем буквы в кругах, так как они фиксированы. Также стираем круги внутри прямоугольников, так как их количество известно — по два круга в каждом прямоугольнике.
В итоге получим такой рисунок:
В процессе решения задачи мы пришли к такой формуле:
Комбинируем приведенные формулы, немного упрощаем и получаем решение:
Выводы
Теперь вы знаете, как решать задачи типа «супружеских пар». С помощью этого метода можно вычислить количество вариантов расположения элементов по условиям, которые мы задали.
Особенность такого метода заключается в том, что для решения можно использовать принцип включения и исключения, который мы изучили ранее.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
