Казалось бы, математика - наука хоть и красивая, но весьма абстрактная, даром что применяется в физике, химии, биологии и прочих естественных науках. Однако, в следующей статье Вы сможете прочитать о том, как однажды капитан воздушного плавания с помощью математики взялся устроить личное счастье себе и ещё 99 своим друзьям, запертым в космическом корабле. В чём весьма и преуспел.


Обратите внимание, на математические вопросы к читателю в конце статьи!



— Сегодня стартовал наш долгий космический полёт, — так начал свою речь капитан первого межзвёздного корабля «Земля — Андромеда». — Нас здесь, как вы знаете, 50 мужчин и 50 женщин, а лететь нам 50 лет. Так что всем следует завести семьи. Каждый из вас не женат и должен вступить в брак здесь: таково было условие приёма в экспедиционный корпус.

— Мы помним, и многие из нас будут рады жениться уже сегодня. Мы знаем друг друга не меньше года.

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

Все рассмеялись от души.

— Капитан, вы идеалист, — сказал кто-то.

— Я вполне реалистичен, — улыбнулся капитан. — Это невозможно на Земле, но мы вполне можем осуществить это здесь.

— Как это? — Все продолжали смеяться.

— Могу я спросить, — капитан был несгибаем, — почему это женатый мужчина А изменяет своей жене с замужней леди О?

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

— И А запросто находит красотку О, которая предпочтет его собственному мужу?

— Проще некуда! — Некоторые уже просто покатывались от хохота.

— Но это на Земле! — Капитан строго посмотрел на команду, и смех сам собой пропал. — А я намерен женить нас так, чтобы никакому мужчине А не удалось найти такую женщину О, которая бы нравилась ему больше собственной жены и которая предпочла бы его собственному супругу.

— Вы имеете в виду, капитан, что каждой такой женщине, которая нравится А больше, чем его половина, сам А не нравится? По крайней мере не больше собственного мужа.

— Именно. И наоборот, А предпочитает свою жену всем тем, которые с радостью сменили бы своих партнёров на него.

— Хорошая идея, капитан! Если вам это удастся, вы решите вековую проблему стабильности в браке. Но нам всё равно кажется, что это невозможно.

— Но могу я попробовать? — спросил капитан вкрадчиво.

— Отчего же нет, это будет забавно!

— Прекрасно! Тогда начнём немедленно. Сегодня каждый мужчина должен выбрать ту женщину, которая ему нравится больше всех, и написать ей письмо: попросить её руки.

— Но тогда все выберут Диану. — Диана Браун была признанной красавицей. Многие были влюблены в неё, но мало кто надеялся стать её мужем.

— Во-первых, не все. Например, не я. Кроме того, это не играет никакой роли. Вы должны посвататься, даже если у вас нет никакого шанса. Выберите ту женщину, о которой мечтаете. Однако это — только начало. Мы продолжим завтра. А сейчас вы должны написать своё первое письмо. И не думайте о возможном отказе. Только выберите самую желанную женщину. И помните: это — приказ. Каждый должен выбрать и посвататься!

Не многие из мужчин смогли уснуть в эту ночь. Выбрать женщину своей мечты. Не так-то это просто! К тому же она может и отказать. Пожалуй, хорошо, что это был приказ, многие иначе и не осмелились бы посвататься. И многие выбрали Диану.



Капитану тоже не спалось. Мэри, в которую он тайно был влюблён, давно уже предпочитала другого.

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

— Вижу, далеко не все получили письма, — заметил капитан. Несколько вздохов были ему ответом. — А кто-то получил больше одного письма. — Некоторые женщины радостно кивнули. Краем глаза он увидел, что и Мэри кивнула тоже. — Теперь ваш черёд выбирать! Каждая женщина, которая получила больше одного письма, должна выбрать только одного мужчину.

— И выйти за него замуж?

— Нет, этого я не говорил. Но вот что вы должны сделать — так это ответить всем остальным, что вы никогда не сможете выйти за них. Я думаю, это естественно. Они должны знать, что есть кто-то, кто вам нравится больше.

— Только это?

— Только это. И ждать завтрашнего дня.

— Тогда Диане придётся писать много писем! — пошутил кто-то в зале. Но самой ей, похоже, было не до шуток.

— А можно, я всем отвечу? — спросила она. «Видать, не получила она того письма, которого ждала», — подумал капитан, а вслух сказал:

— Нет, ты должна ответить всем, кроме лучшего из них. Это только начало. Мы всего лишь отметаем заведомо нестабильные браки, — попытался он утешить красавицу. Только в последнюю секунду он осмелился поднять взгляд на Мэри. Она сочувственно улыбнулась ему, и он понял, что завтра получит от неё письмо. Мало кому удалось легко уснуть и в эту ночь. Женщины, которым было из чего выбирать, размышляли. Те, кому вообще выбирать было не из чего, плакали. А мужчины... Мужчины ждали и тоже не могли уснуть.

На следующее утро больше половины из них получили письма, и большую часть — от Дианы. Письма были вежливые, но безнадёжные. Капитан также получил своё письмо от Мэри. После завтрака все собрались, и капитан сказал:

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

— Вы правы, капитан! — большинство были согласны.

— А вы знаете, что нам делать теперь?

— Нет, не знаем.

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



— Значит, мы можем получить новое письмо? — спросили женщины с радостью в голосе.

— Да. И, может быть, не одно.

— И те, что уже получили письма, тоже могут?

— Конечно! С одним лишь исключением: вы не получите писем от тех, кому отказали. Но вряд ли вам нужны эти письма.

— Капитан, вы умнее, чем мы думали!

Новые надежды — новые радости. Женщины оживились.

— А если мужчине не отказали, значит ли это, что он уже может заказывать кольца? — спросил довольный молодой человек. Многие подозревали, что он был единственным, кто написал Диане и не получил никакого письма в ответ.

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

— Совершенно верно, — подтвердил капитан. — Но если хочешь, ты можешь написать той же женщине.

— Я так и сделаю!

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

— И зачем я это начал? — спрашивал он себя. — Сам же убил свою надежду... Однако в любом случае я должен выбрать новую женщину. И получить ещё одно письмо. Потому что я должен быть честным: Диана — лучше всех, если я должен позабыть про Мэри. — И он написал и отослал письмо Диане.

На следующее утро большинство женщин были веселы, а Диана просто светилась от радости.

«Наверное, она получила то письмо, на которое надеялась», — подумал капитан, а вслух сказал:

— Девушки, те, кто получил больше одного письма, знают, что надо делать?

— Выбрать лучшего и ответить остальным.

— Умницы!

— Но, капитан, как долго мы будем писать и выбирать?

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

— Капитан, — сказала Мэри,— кажется, я поняла, наконец, твою идею. Ты имеешь в виду, что мы, женщины, не будем неверны мужьям по той простой причине, что те, с кем мы могли бы это, возможно, сделать, не любят нас: они не прислали нам письма, у них есть кто-то лучше. А если ни одна женщина не будет неверна, то не будет и неверных мужей.

— Прекрасное рассуждение!

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



— Ты можешь быть уверена в этом! Всем остальным ты всё равно откажешь.

— Зачем же мне тогда ждать?

— Только для того, чтобы все остальные тоже получили своё письмо.

— Но могу я уже сейчас сказать моему будущему спутнику жизни, что я выбрала его до конца своих дней?

— Я думаю, ты должна это сказать и другим: они не будут тогда к тебе свататься и найдут свою пару быстрее.

— Тогда не хочу я больше писать никаких писем! — сказала Диана и нежно поцеловала оторопевшего капитана.

***

Хочется верить, что читатель понял ту математическую проблему, которая лежит в основе этой сказки. Мы надеемся, читатель согласится, что это — красивое решение, и спросит себя: как его можно использовать? И как решать похожие проблемы? Например, что будет, если женщин больше, чем мужчин, или если есть мужчины, которые скорее умрут, чем женятся? А если женщины будут писать первыми, будет ли решение тем же самым? Если же читатель задумается: «Правда ли это? Могу ли я, например, доказать, что все найдут себе супруга?» — значит, он начал думать как математик. А тогда несколько задач должны быть приятным дополнением к сказке.

1. Сформулируйте задачу строго математически. Это может оказаться сложнее, чем ожидалось. Не отступайте! Начните так: даны две квадратные таблицы размером n x n. В каждой строке каждой из таблиц стоят все числа от 1 до n в каком-то порядке...

2. Напишите чёткий алгоритм, который соответствует решению в сказке, и покажите, что он всегда работает.

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

4. Предположим теперь, что таблицы бесконечные, занумерованы натуральными числами и что в каждой строке есть все натуральные числа. Можно ли тогда доказать существование решения, если предполагать, что в каждой строке кандидаты расположены в порядке убывания предпочтения (в частности, на первом месте каждой строки стоит номер самого лучшего кандидата)?

5. А если порядок противоположный?

6. Рассмотрите ещё и такой алгоритм для исходной (конечной) задачи. Разрешим разводы. Выстроим всех мужчин в очередь. Первый в очереди сватается ко всем женщинам по очереди в порядке своего предпочтения (независимо от того, замужем очередная кандидатура или нет) до тех пор, пока кто-то не согласится. Они женятся, и если женщина была замужем, то она сначала разводится, а её бывший супруг становится в конец очереди. Верно ли, что:

а) такая женщина всегда найдётся;

б) процесс закончится;

в) получившиеся браки будут стабильными?

г) Годится ли такой подход для бесконечных случаев?