Обратите внимание, на математические вопросы к читателю в конце статьи!
— Сегодня стартовал наш долгий космический полёт, — так начал свою речь капитан первого межзвёздного корабля «Земля — Андромеда». — Нас здесь, как вы знаете, 50 мужчин и 50 женщин, а лететь нам 50 лет. Так что всем следует завести семьи. Каждый из вас не женат и должен вступить в брак здесь: таково было условие приёма в экспедиционный корпус.
— Мы помним, и многие из нас будут рады жениться уже сегодня. Мы знаем друг друга не меньше года.
— Хорошо. Но я думаю, что жениться должны все, причём так, чтобы на этом корабле не было никаких супружеских измен.
Все рассмеялись от души.
— Капитан, вы идеалист, — сказал кто-то.
— Я вполне реалистичен, — улыбнулся капитан. — Это невозможно на Земле, но мы вполне можем осуществить это здесь.
— Как это? — Все продолжали смеяться.
— Могу я спросить, — капитан был несгибаем, — почему это женатый мужчина А изменяет своей жене с замужней леди О?
— Что же здесь непонятного, капитан? Потому что они нравятся друг другу больше, чем их собственные супруги.
— И А запросто находит красотку О, которая предпочтет его собственному мужу?
— Проще некуда! — Некоторые уже просто покатывались от хохота.
— Но это на Земле! — Капитан строго посмотрел на команду, и смех сам собой пропал. — А я намерен женить нас так, чтобы никакому мужчине А не удалось найти такую женщину О, которая бы нравилась ему больше собственной жены и которая предпочла бы его собственному супругу.
— Вы имеете в виду, капитан, что каждой такой женщине, которая нравится А больше, чем его половина, сам А не нравится? По крайней мере не больше собственного мужа.
— Именно. И наоборот, А предпочитает свою жену всем тем, которые с радостью сменили бы своих партнёров на него.
— Хорошая идея, капитан! Если вам это удастся, вы решите вековую проблему стабильности в браке. Но нам всё равно кажется, что это невозможно.
— Но могу я попробовать? — спросил капитан вкрадчиво.
— Отчего же нет, это будет забавно!
— Прекрасно! Тогда начнём немедленно. Сегодня каждый мужчина должен выбрать ту женщину, которая ему нравится больше всех, и написать ей письмо: попросить её руки.
— Но тогда все выберут Диану. — Диана Браун была признанной красавицей. Многие были влюблены в неё, но мало кто надеялся стать её мужем.
— Во-первых, не все. Например, не я. Кроме того, это не играет никакой роли. Вы должны посвататься, даже если у вас нет никакого шанса. Выберите ту женщину, о которой мечтаете. Однако это — только начало. Мы продолжим завтра. А сейчас вы должны написать своё первое письмо. И не думайте о возможном отказе. Только выберите самую желанную женщину. И помните: это — приказ. Каждый должен выбрать и посвататься!
Не многие из мужчин смогли уснуть в эту ночь. Выбрать женщину своей мечты. Не так-то это просто! К тому же она может и отказать. Пожалуй, хорошо, что это был приказ, многие иначе и не осмелились бы посвататься. И многие выбрали Диану.
Капитану тоже не спалось. Мэри, в которую он тайно был влюблён, давно уже предпочитала другого.
— Но я должен написать Мэри, — тяжело вздохнул капитан и начал своё письмо. На следующее утро после завтрака все собрались в зале. Многие женщины были тихи и печальны.
— Вижу, далеко не все получили письма, — заметил капитан. Несколько вздохов были ему ответом. — А кто-то получил больше одного письма. — Некоторые женщины радостно кивнули. Краем глаза он увидел, что и Мэри кивнула тоже. — Теперь ваш черёд выбирать! Каждая женщина, которая получила больше одного письма, должна выбрать только одного мужчину.
— И выйти за него замуж?
— Нет, этого я не говорил. Но вот что вы должны сделать — так это ответить всем остальным, что вы никогда не сможете выйти за них. Я думаю, это естественно. Они должны знать, что есть кто-то, кто вам нравится больше.
— Только это?
— Только это. И ждать завтрашнего дня.
— Тогда Диане придётся писать много писем! — пошутил кто-то в зале. Но самой ей, похоже, было не до шуток.
— А можно, я всем отвечу? — спросила она. «Видать, не получила она того письма, которого ждала», — подумал капитан, а вслух сказал:
— Нет, ты должна ответить всем, кроме лучшего из них. Это только начало. Мы всего лишь отметаем заведомо нестабильные браки, — попытался он утешить красавицу. Только в последнюю секунду он осмелился поднять взгляд на Мэри. Она сочувственно улыбнулась ему, и он понял, что завтра получит от неё письмо. Мало кому удалось легко уснуть и в эту ночь. Женщины, которым было из чего выбирать, размышляли. Те, кому вообще выбирать было не из чего, плакали. А мужчины... Мужчины ждали и тоже не могли уснуть.
На следующее утро больше половины из них получили письма, и большую часть — от Дианы. Письма были вежливые, но безнадёжные. Капитан также получил своё письмо от Мэри. После завтрака все собрались, и капитан сказал:
— Сегодня многие из нас получили письмо. Это означает, что мы, — капитан бросил печальный взгляд на Мэри, — не имеем никаких шансов на стабильный брак с нашими избранницами. И я считаю, что лучше узнать это сейчас, чем после женитьбы.
— Вы правы, капитан! — большинство были согласны.
— А вы знаете, что нам делать теперь?
— Нет, не знаем.
— Во-первых, забыть эту женщину. Вы никогда не женитесь на ней. Во-вторых, выбрать самую лучшую женщину из оставшихся и посвататься к ней!
— Значит, мы можем получить новое письмо? — спросили женщины с радостью в голосе.
— Да. И, может быть, не одно.
— И те, что уже получили письма, тоже могут?
— Конечно! С одним лишь исключением: вы не получите писем от тех, кому отказали. Но вряд ли вам нужны эти письма.
— Капитан, вы умнее, чем мы думали!
Новые надежды — новые радости. Женщины оживились.
— А если мужчине не отказали, значит ли это, что он уже может заказывать кольца? — спросил довольный молодой человек. Многие подозревали, что он был единственным, кто написал Диане и не получил никакого письма в ответ.
— Нет, этого капитан не имел в виду. Ты просто имеешь хороший шанс, но надо ещё подождать, — ответила Диана ко всеобщему изумлению.
— Совершенно верно, — подтвердил капитан. — Но если хочешь, ты можешь написать той же женщине.
— Я так и сделаю!
Новый выбор — новая надежда. Но на этот раз многие спали хорошо. Только некоторые из тех, кто получил отказ, не могли уснуть. Среди них был и капитан.
— И зачем я это начал? — спрашивал он себя. — Сам же убил свою надежду... Однако в любом случае я должен выбрать новую женщину. И получить ещё одно письмо. Потому что я должен быть честным: Диана — лучше всех, если я должен позабыть про Мэри. — И он написал и отослал письмо Диане.
На следующее утро большинство женщин были веселы, а Диана просто светилась от радости.
«Наверное, она получила то письмо, на которое надеялась», — подумал капитан, а вслух сказал:
— Девушки, те, кто получил больше одного письма, знают, что надо делать?
— Выбрать лучшего и ответить остальным.
— Умницы!
— Но, капитан, как долго мы будем писать и выбирать?
— До тех пор, пока каждая из вас не получит хотя бы одно письмо. И тогда лучшее письмо будет от вашего будущего мужа. И это будет стабильный брак. Подумайте, почему.
— Капитан, — сказала Мэри,— кажется, я поняла, наконец, твою идею. Ты имеешь в виду, что мы, женщины, не будем неверны мужьям по той простой причине, что те, с кем мы могли бы это, возможно, сделать, не любят нас: они не прислали нам письма, у них есть кто-то лучше. А если ни одна женщина не будет неверна, то не будет и неверных мужей.
— Прекрасное рассуждение!
— Можно спросить? — сказала Диана. — Означает ли это, что я буду замужем за тем единственным человеком, которого люблю, если он уже написал мне?
— Ты можешь быть уверена в этом! Всем остальным ты всё равно откажешь.
— Зачем же мне тогда ждать?
— Только для того, чтобы все остальные тоже получили своё письмо.
— Но могу я уже сейчас сказать моему будущему спутнику жизни, что я выбрала его до конца своих дней?
— Я думаю, ты должна это сказать и другим: они не будут тогда к тебе свататься и найдут свою пару быстрее.
— Тогда не хочу я больше писать никаких писем! — сказала Диана и нежно поцеловала оторопевшего капитана.
***
Хочется верить, что читатель понял ту математическую проблему, которая лежит в основе этой сказки. Мы надеемся, читатель согласится, что это — красивое решение, и спросит себя: как его можно использовать? И как решать похожие проблемы? Например, что будет, если женщин больше, чем мужчин, или если есть мужчины, которые скорее умрут, чем женятся? А если женщины будут писать первыми, будет ли решение тем же самым? Если же читатель задумается: «Правда ли это? Могу ли я, например, доказать, что все найдут себе супруга?» — значит, он начал думать как математик. А тогда несколько задач должны быть приятным дополнением к сказке.
1. Сформулируйте задачу строго математически. Это может оказаться сложнее, чем ожидалось. Не отступайте! Начните так: даны две квадратные таблицы размером n x n. В каждой строке каждой из таблиц стоят все числа от 1 до n в каком-то порядке...
2. Напишите чёткий алгоритм, который соответствует решению в сказке, и покажите, что он всегда работает.
3. Покажите, что бывают случаи, когда задача имеет несколько решений.
4. Предположим теперь, что таблицы бесконечные, занумерованы натуральными числами и что в каждой строке есть все натуральные числа. Можно ли тогда доказать существование решения, если предполагать, что в каждой строке кандидаты расположены в порядке убывания предпочтения (в частности, на первом месте каждой строки стоит номер самого лучшего кандидата)?
5. А если порядок противоположный?
6. Рассмотрите ещё и такой алгоритм для исходной (конечной) задачи. Разрешим разводы. Выстроим всех мужчин в очередь. Первый в очереди сватается ко всем женщинам по очереди в порядке своего предпочтения (независимо от того, замужем очередная кандидатура или нет) до тех пор, пока кто-то не согласится. Они женятся, и если женщина была замужем, то она сначала разводится, а её бывший супруг становится в конец очереди. Верно ли, что:
а) такая женщина всегда найдётся;
б) процесс закончится;
в) получившиеся браки будут стабильными?
г) Годится ли такой подход для бесконечных случаев?
("Квантик" №1, "Стабильные браки", Виктор Уфнаровский,
материал впервые опубликован в журнале "Квант" №3 за 2009 год)
