задачи о замужестве
Так как я недавно вышла на брачный рынок установила апп знакомств на телефон и озаботилась проблемой, когда говорить "да", а когда "нет", вспомнились две математических задачки. На самом деле, обе задачки достаточно важными оказались в математике 20ого века, но я расскажу про самые простые формулировки и их решения.
Задача о разборчивой невесте.
Невесте нужно выбрать лучшего из возможных жениха. Она точно знает, что их 1000, и они один за другим будут ей представлены до тех пор, пока она не скажет "да". Если же невеста сказала "нет", гордый жених уезжает, и поменять свое мнение невеста не может. В задаче есть предположение (в жизни трудно реализуемое или скорее трудно вычисляемое), что женихов можно упорядочить по привлекательности, то есть существует один-единственный самый хороший, существует второй по привлекательности, третий и так далее. Женихи предстают перед нашей красавицей в случайном порядке. Вопрос - какая оптимальная стратегия у невесты?
Оказывается, оптимальная стратегия такая - сначала всем говорить "нет", набирать статистику, а потом сказать "да" первому из тех, кто лучше всех-всех, кого принцесса уже успела посмотреть. То есть, скажем, если бы принцесса хотела набрать статистику из двух людей, она бы посмотрела, поставила им оценки, а если третий лучше обоих, сказала бы ему "да", и остальных не увидела бы. Если третий хуже хотя бы одного, то она перешла бы к четвертому, которого опять бы сравнивала с первыми двумя, и так далее. Оказывается, оптимальное число кандидатов для набора статистики практически одна треть от имеющегося числа кандидатов. То есть на первых чуть больше 300 принцесса просто смотрит, и запоминает самого крутого, а всех после этого сравнивает с самым крутым, и если он лучше, выходит замуж.
Понятно, что тут много предположений в самой формулировке, которые в жизни не выполняются, но здравое зерно в этом решении возможно и есть, особенно для пользователей тиндера.
Задача о марьяже.
Из совсем другой области математики. Есть одинаковое число мужчин и женщин, они в отличие от нашей принцессы, сначала друг друга хорошенько рассмотрели и точно решили, у кого из всего множества потенциальных партнеров какой приоритет. То есть у каждой женщины существует список, в который включены все мужчины, и тот, кто записан первым номером - самый желанный, а последний - совсем нет, но тоже сойдет часики же тикают. И у мужчин есть такой список с женщинами. Вопрос такой - как всех переженить, чтобы никогда не существовало такой ситуации, что жену из одной пары и мужа из другой тянуло друг к другу сильнее, чем к своим партнерам.
Оказывается, нужно сделать вот что. В первом раунде мужчины делают предложения первой даме в своем списке. Каждая дама либо получает несколько предложений, либо не получает совсем. Если предложение делает мужчина, который у этой женщины первый в списке, то она сразу же соглашается, и образуется пара. Если же первый из списка предложение не делает, то женщина говорит, что ей нужно подумать самому лучшему, а остальным отказывает. Затем происходит второй раунд, где получившие отказ мужчины переходят ко второй женщине в списке, а женщина повторяет стратегию предыдущего раунда с той лишь разницей, что если новый мужчина лучше того, кому она раньше сказала "может быть", эти старые "может быть" получают апдейт в виде "нет", и участвуют в следующем раунде (прошлый они пропустили, потому что ждали апдейта). Если же новый мужчина хуже того, кто ждет ответ сейчас, он получает "нет". Таким образом, если повторить достаточное число раз эту процедуру, все переженятся. Естественно, когда мужчин с "нет" не осталось в природе, мужчины с "может быть" получают апгрейд в виде "да".
Эта задача, пожалуй, более жизненная - есть конкуренция, можно немного рассмотреть кандидатов и вернуться к понравившемуся. Решение тоже более интуитивно понятное. В ней также есть еще один интересный эффект - мужчиной быть лучше. То есть тем, кто делает предложение. В современном мире, девушки могут сами звать на свидание, и задача может быть сформулирована так, что мужчины и женщины меняются местами.