Оригинал взят у rubtsov в Задачи, которые волнуют девушек Я тут в твиттере спалился, что у меня есть две задачи, при обсуждение которых женская часть аудитории всегда реагирует бодро. После чего мужская часть моих читателей твиттера тут же начала с меня требовать эти задачи. Придётся здесь описать подробно их формулировки. Задача о неверных жёнах На острове жители пустились в разврат настолько, что бургомистр решил всё это прекратить. Для этого он собрал всех жителей в одном отеле и сказал, что запрёт все семейные пары по комнатам и откроет двери только тогда, когда все неверные жёны будут убиты. Он установил в отеле радио, которое каждый день ровно в полдень будет в каждой комнате объявлять сколько женщин было убито за прошлый день. Разумеется, жёны (даже верные) прекрасно в курсе того кто когда и с кем, поэтому если неверных жён на острове M, то верная жена на вопрос «сколько на острове неверных жён» будет отвечать правду (то есть M), а неверная будет готова посчитать всех, кроме себя, поэтому на тот же вопрос ответит M-1. Цель мужей — убить всех неверных жён, и не убить ни одну неверную — как им сговориться заранее (до того как их закроют по комнатам), чтобы достичь цели? Я про эту задачу узнал в институте, наверное курсе на третьем и решение придумал относительно быстро — где-то за день или даже за вечер. На самом деле эта задача школьная, так что можете над ней подумать :) Задача о том, почему так трудно успешно выйти замуж Для затравки скажу, что речь идёт об алгоритме Гейла-Шепли , за который дали Нобелевскую премию по экономике в 2012 году. В пересказе на дела любовные, задача звучит так. Есть деревня, в которой сельский староста решил всех молодых переженить, да так, чтобы семейные пары не разбежались. Задача состоит в том, чтобы найти алгоритм, который решает эту задачу. Для этого он попросил каждого парня выстроить всех девушек в список в порядке предпочтения, а девушек составить список парней (эти списки являются входом алгоритма). Условие того, что пара разбегается состоит в том, что в двух сформированных парах есть парень и девушка, которые могут сформировать более счастливую пару — так, что оба беглеца будут в ней более счастливы. Решение задачи состоит в следующем. Бургомистр направляет парней к девушкам в порядке их приоритета. Девушка, если к ней пришёл парень мечты сразу говорит «Да». Если же к ней пришёл не самый лучший вариант, то она говорит «ой, я подумаю», затем если всех женихов в списке выше разобрали, то она говорит «Да» тому кто выше всех в списке, среди тех, кому она сказала «я подумаю». Таким образом образуются семейные пары, которым нет смысла разбегаться — все лучшие варианты уже заняты более лучшими для них вариантами. И при этом выполняется следующая закономерность — парень всегда получает лучшую девушку, среди тех, чьего сердца он может добиться, при текущей конкуренции, а девушка получает не самого лучшего парня, из тех, на которых могла бы расчитывать. Обе эти задачи мгновенно вызывают женскую критику на мужской шовинизм, хотя аналогии в общем-то жизненные. И, кстати, благодаря второй задаче люди находят доноров по пересадке почке: в семейной жизни, женский организм обычно вырабатывает антитела, поэтому почка мужа часто не приживается (не помню работает ли отторжение в обратную сторону), в итоге есть много пар, которые ищут подходящих партнёров для обмена почками, кроме того есть вероятность отторжения, поэтому требуется формировать устойчивые пары.