игра
сыграл бы в эту игру
- ты ведь, наверно, слышала про алгоритм Гейла-Шепли (Gale-Shapley)?
Вкратце, там так: каждый из n мальчиков и n девочек упорядочивает всех участников противоположного пола в порядке
убывания привлекательности. Наша задача разбить их на пары, так чтобы ситуация была стабильна, то есть не было бы мальчика и девочки, которые предпочитают друг друга своим партнерам.
Оказывается, что это всегда возможно. В первом раунде каждый мальчик делает предложения первой девочке в своем списке. Девочки, у которых есть предложения, выбирают лучшее (в соответствие со своим списком) и обручаются. Во втором раунде все отвергнутые мальчике делают предложения следующим девочкам в своих списках. Девочки, получившие предложения опять выбирают лучшее. Это так же относится к уже обрученным - они выбирают лучшего среди сделавших предложение и текущего жениха. Ну и так далее.
Это все заканчивается стабильной разбивкой на пары. Что интересно, в результате этого алгоритма, каждая девочка оказывается в самом плохом браке (из всех для нее возможных при стабильной разбивке на пары), а у мальчиков все наоборот. Конечно, если поменять роли, алгоритм становится оптимальным для девочек.
По-моему, очень убедительно, надо делать предложения, а не ждать их.