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