Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Задача о супружеских парах Комбинаторика

eyJpZCI6IjQ5NWRiM2MxOTJjZmRmYTBkMjI5N2JiY2EzMDJjN2YyLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=1cb3ee111004ebd3e7a9acf4baa7b2c9041eb4853592b9a116812a36c49857ff

Представим, что вы организуете круглый стол, и вам важно, в каком порядке будут рассажены участники. В комбинаторике такую задачу называют «задачей о супружеских парах» или методом Le Problème des Ménages.

В этом уроке разберем, как работает такой метод.

Решаем задачу о супружеских парах

Для начала рассмотрим самую распространенную формулировку этой задачи:

Допустим, у нас есть пар, каждая из которых состоит из мужчины и женщины.

Их нужно рассадить за круглым столом так, чтобы мужчины и женщины чередовались. При этом женщины должны сидеть на нечетных местах и ни одна из них не может сидеть рядом со своим партнером.

Нужно вычислить, сколько существует вариантов рассадки.

Чтобы решить эту задачу, используем принцип включения и исключения.

Для начала переведем задачу на язык математики и присвоим имена:

  • Пусть — множество пар

  • При этом — множество рассадок, в которых женщины занимают нечетные места

  • Нужно найти те члены в , для которых ни одна пара не сидит вместе

  • Выражение обозначим через множество расстановок

  • Множество обозначает пары из множества , которые нарушают правило

  • По симметрии размер зависит от размера , а не от конкретного выбора пар

  • Поэтому сделаем такой вывод — если , обозначим

Далее находим нужное число. Для этого применим принцип включения и исключения:

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

Наши плохих пар могут располагаться над плохими парами мест способами. Поэтому мы приходим к такому выражению:

После этого мы можем рассадить оставшихся женщин способами, а оставшихся мужчин — способами.

Вот так может выглядеть схема рассадки:

eyJpZCI6ImIyNzk2MTU0NGMzMjAyZTRmYzA4NTI4NmRjMWEwYmIxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=34499dbfd0890377ea2886de49cd8c34c82c752061034b4c594105296ef17edf

Здесь три пары сидят вместе, что не соответствует первоначальному условию рассадки.

Остается определить . Для этого разорвем окружность в фиксированной точке. Далее сотрем буквы в кругах, так как они фиксированы. Также стираем круги внутри прямоугольников, так как их количество известно — по два круга в каждом прямоугольнике.

В итоге получим такой рисунок:

eyJpZCI6IjFkY2VlYzRhNmNiYmFiZGU3M2NjM2VhZjU1ZTQ4MTlmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=bbc3f89b0397da92806c29a0125b4aca7b7e87c9fd185874d3f26aaea6458bdd

В процессе решения задачи мы пришли к такой формуле:

Комбинируем приведенные формулы, немного упрощаем и получаем решение:

Выводы

Теперь вы знаете, как решать задачи типа «супружеских пар». С помощью этого метода можно вычислить количество вариантов расположения элементов по условиям, которые мы задали.

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


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

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