Сбежав из Владивостока, вы возвращаетесь к невесте — тоже шпионке мирового уровня. Подготовка к знаменательному событию, которое все ближе и ближе, у вас под контролем. Осталось несколько нерешенных моментов, и один из них — как рассадить гостей на свадебном завтраке. Помимо родственников, которые не ладят между собой, у вас с будущей супругой есть несколько друзей — агентов под глубоким прикрытием. Друг с другом они тоже знакомы, но этот факт необходимо скрыть, а значит, их не должны увидеть сидящими рядом. Существует ли математический метод, который позволил бы гарантированно, без проб и ошибок рассадить гостей так, как надо? Любой просчет возымеет далеко идущие политические последствия и перечеркнет многолетнюю разведывательную работу.

Желание рассадить гостей строго по науке могло бы показаться странным, однако математиков издавна занимают проблемы такого рода. К примеру, так называемая задача о гостях («задача о супружеских парах»), которую сформулировали еще в конце XIX века, звучала примерно так: сколькими способами можно рассадить гостей за круглым столом при условии, что лица одного пола и супружеские пары не должны сидеть рядом друг с другом?

Формулировка проста, но ответ был найден далеко не сразу. Почему? Отчасти потому, что в те времена даже для математиков, которые решали задачу лишь на бумаге, казалось немыслимым не усадить дам в первую очередь. Это настолько усложнило задачу, что лишь через 40 лет французский математик Жак Тушар предложил первый вариант ее решения. Альтернативную и более простую (скажем так, «несексистскую») версию в 1985 году обнародовали американцы Кеннет Богарт и Питер Дойл.

Еще одна головоломка под названием задача Обервольфаха, придуманная в 1967 году немецким математиком Герхардом Рингелем, связана с распределением мест на обедах. На конференциях, которые проводятся в математическом институте Обервольфаха (Германия), принято обедать в общем зале. Вопрос был поставлен так: каким образом следует рассадить участников за столами разных диаметров, чтобы в течение всего многодневного мероприятия гости не соседствовали более одного раза? На сегодня уже установлено, что количество приглашенных должно быть нечетным, кроме того, исключены несколько комбинаций столов. Однако до конца задача не решена. Сумеете ли вы придумать, как оптимально рассадить гостей, если даже профессиональные математики вот уже более века едва-едва справляются с аналогичной проблемой?

Можете ответить, что да, но имейте в виду: за помощью придется обратиться к другу компьютеру. Итак, сначала вы оцениваете связи гостей — создаете таблицу и начисляете очки каждому приглашенному. Не знакомые друг с другом не получают ничего, знакомые — по единице. Убедитесь, что пары, состоящие в отношениях, окажутся по соседству, и дайте им по 50 очков, а тем, кто, напротив, не ладит между собой, по –50: так вы поймете, что им вообще не нужно сидеть за одним столом. Еще вам, разумеется, не хочется, чтобы ваши друзья, принадлежащие к противодействующим разведсообществам, чувствовали себя не в своей тарелке. Попробуйте начислять очки как-то еще — допустим, для обозначения степени родства и так далее. Неполная таблица может выглядеть следующим образом:

A и B — супружеская пара, A — брат жениха. C и D состоят в отношениях, D — двоюродный брат невесты. E — тетя жениха, которая когда-то встречалась с D, однако расстались они не слишком хорошо. Такая таблица называется матрицей связей (матрица — математическое название массива из чисел, записанного в виде прямоугольной таблицы).

Охарактеризовав соответствующим образом взаимоотношения приглашенных, вы рассматриваете все существующие варианты распределения мест. Затем суммируете очки гостей, сидящих за одним столом, и оцениваете, какая из компоновок наберет больше остальных. Если бы все пятеро гостей, которые фигурируют в матрице-примере, сидели вместе, их совокупный счет равнялся бы 2: два по 50 от пар A/B и C/D были бы сведены на нет соседством C и D с E. Таким образом, остались бы только два по 1 от E, знакомой с A и B.

Прежде, чем прикидывать, сколько времени уйдет на составление более или менее жизнеспособного плана рассадки, давайте определим количество возможных вариантов. Чтобы решить эту задачу, нужно знать общее количество приглашенных (n) и количество мест за каждым столом (t). Предположим, что заполнены будут все столы, имеющие при этом одинаковый размер.

На свадьбе ожидаются 104 человека, а каждый стол рассчитан на восьмерых. Если рассаживать гостей как придется, у первого из них будет 104 варианта, у второго — 103, 102 — для третьего и так далее. Таким образом, количество вариантов для первого стола будет равно:

104 × 103 × 102 × 101 × 100 × 99 × 98 × 97 =
= 10 385 445 095 625 600.

Только для первого стола получается более 10 триллионов вариантов! Если взять все 13 столов, то у нас будет по-настоящему грандиозное число — со 166 нулями. Впрочем, некоторые варианты распределения мест совпали бы: за один и тот же стол, пусть и в другом порядке, уселись бы все те же восемь человек. Эту «восьмерку» можно разместить 40 320 способами, поскольку у нас есть восемь мест для первого человека, семь для второго и так далее:

8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 320.

В математике есть форма краткой записи для вычислений, о которых рассказывается выше: знак факториала. Видим n! — понимаем, что нужно перемножить между собой все положительные целые числа, вплоть до n. Левую часть вышеприведенного выражения можно записать как 8!.

Давайте допустим, что первый стол можно заполнить 10 385 445 095 625 600 ÷ 40 320 = 257 575 523 205 способами. Всего-то 257 миллиардов с небольшим! Но у математиков есть сокращенная формула и для подобной комбинаторной задачи на число сочетаний n по k — где n — количество элементов, из которых вы выбираете (в нашем случае, это число приглашенных на свадьбу), а k — количество элементов в сочетании. Формула для

Прогоним ее на только что рассмотренном примере. Мы выбираем 8 из 104, поэтому принимаем n = 104, а k = 8:

Это дает:

Вычисляем:

Ничего удивительного.

Понятно, что количество сочетаний даже для одного-единственного стола — чудовищное. Что делать? Вот тут-то в игру и вступает друг компьютер. Существует коммерческое ПО, рассчитанное на работу как раз с такими задачами — задачами линейного программирования. Эти программы можно применять для самых разных целей: например, для определения, какой продукт и в каком количестве должна выпускать компания, чтобы извлечь максимальную прибыль. Организаторы свадеб пользуются ими для решения таких же проблем, как ваша.

В 2012 году два академика из Принстонского университета Меган Беллоуз и Люк Питерсон при помощи вышеупомянутого метода нашли, как распределить за 10 столами 107 гостей. Чтобы просчитать все комбинации, компьютеру понадобилось 36 часов: результат — с минимальными изменениями — был одобрен матерью невесты (а кто еще обо всем позаботится?).

Поставив себе на службу чудеса линейного программирования, вы просите компьютер показать все возможные комбинации, одновременно подсчитывая очки из матрицы связей. Вариант, который наберет наибольшую сумму очков, и станет лучшим — именно так вы сможете рассадить гостей на свадьбе и не «спалите» тайных агентов. Вы счастливы, что сбросили с плеч эту ношу, и переходите к другой сложной задаче — сочинить такую свадебную речь, которая не разожжет международный скандал.