Задача Озанама: комбинаторная головоломка XVII века о семи друзьях
Задача Озанама, или «Проблема семи друзей за обедом» — стала классическим примером в комбинаторике.
Она была впервые сформулирована французским математиком Жаком Озанамом (1640–1718) в его знаменитом труде «Математические и физические развлечения» (четыре энциклопедических тома) «Récréations mathématiques et physiques» (1694).
Эта работа стала одним из первых систематических сборников математических развлечений и выдержала не менее десяти переизданий. Она стала предтечей большинства книг по занимательной математике на ближайшие два столетия.
«Семь друзей собираются на обед, но между ними возникает спор о рассадке. Чтобы уладить спор, они договариваются менять порядок рассадки, пока не переберут все возможные варианты. Вопрос: сколько раз им придётся обедать вместе, чтобы перебрать все комбинации?»
Задача о семи друзьях относится к области комбинаторики — раздела математики, изучающего дискретные структуры, их расположение и комбинирование. Конкретно эта проблема связана с понятием перестановок — различных способов упорядочения элементов множества. Для n элементов количество возможных перестановок равно n! (n-факториал).
Таким образом, для семи друзей количество возможных рассадок составляет:
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
Это означает, что друзьям потребуется 5040 обедов, чтобы перебрать все возможные варианты рассадки. Озанам дал именно такой ответ, что это займёт 5040 : 365 ≈ 13,8 лет.
Он исходил из линейной рассадки (7 мест в ряд по одной стороне стола), что было характерно для формальных обедов XVII века, где гости сидели по рангу. Однако в более поздних изданиях (1723 г.) его последователи добавили вариант с круглым столом. Круглые столы ассоциировались с неформальными собраниями.
Форма стола и способ посадки кардинально изменяют математическую суть задачи.
Круглый стол (без учёта зеркальных отражений) можно решить так:
Фиксируем одного человека (чтобы исключить вращения, которые не дают новых рассадок). Остаётся 6 мест, которые можно заполнить 6! = 720 способами. Это стандартный современный подход.
Круглый стол с учётом зеркальной симметрии (если рассадка «по часовой стрелке» и «против» считаются одинаковой): дополнительно делим на 2, 6!/2 = 360 перестановок. В этом случае друзьям хватило бы всего одного года, чтобы опробовать все варианты.
Похожую задачу о рассадке семи друзей за круглым столом (из книги Генри Э. Дьюдени «Кентерберийские Головоломки») мы вам уже предлагали, но там были другие условия.