Задачка: Влияние отказа носить обручальные кольца на время образования новых пар
Если есть программисты или математики, посчитайте сколько итераций знакомств произойдет во второй и третей игре по сравнению с первой. Игра ниже. Пост навеян обсуждением с одним товарищем. Суть: влияние отказа носить обручальные кольца на время образования новых пар Вредная идея: Женатым и замужним носить кольца необязательно
Игра-задачка:
Пусть есть 100 М и 100 Ж. Сыграем в игру (№1). Они стоят друг перед другом в ряд. М или Ж должны одеть кольца на палец свободному партнеру и заодно себе. За раз ходит только один М или Ж, без разницы, пока все пары не станут с кольцами. Первый мужчина (М1) выбирает седьмую женщину (Ж7). Они одевают кольца. Вторая женщина (Ж2) выбирает пятнадцатого мужчину (М15). Затем третий мужчина (М3) хотел бы выбрать Ж2, но видит кольцо, поэтому выбирает Ж3. И так далее. В этом варианте пары образуются довольно быстро. Для математиков: пусть на попытку образования пары тратится время t (для упрощения партнер не может отказать одевать кольцо, если он свободен). Тогда для нашей игры нужно 100*t времени, т.к. каждый раз партнер легко находит не занятого другого партнера.
Теперь вторая игра.
Всё то же самое, только после одевания колец партнеры прячут кольца в карман, а потом, когда к ним подходят другие партнеры, отказывают им. Тогда в примере выше М3 подойдет к Ж2, т.к. у нее нет кольца. Ж2 откажет ему, ведь кольцо в кармане. М3 расстроится, но пойдет к Ж3 и оденет ей кольцо. В данном случае М3 понадобилось 2t времени для образования пары. А теперь представьте, что уже хотя бы половина пар образованы. Тогда следующий допустим М56 будет перед собой иметь ряд Ж1-100 у половины из которых кольцо в кармане. Ему может понадобиться и 2 и 5 и больше подходов, чтобы найти ту самую свободную Ж. Всё ещё хуже, когда свободных остается только 25%. Они вообще как слепые котята будут тыкаться. Мне кажется тут какая-то геометрическая прогрессия. И времени понадобиться в сотни раз больше чем 100t.
А если ещё поиграть в 3ю игру, где добавить фактор возможного отказа (не понравился(-ась)) в 50% случаев, то время ещё затягивается. В том числе и в первой игре будет пересчет.
И для продвинутых 4ая игра. Добавляем фактор: скорее всего сначала выбирают самых востребованных, то есть тех, кто уже занят. Тут необходимо определиться с алгоритмом выборки. Я его не придумал быстро. Может быть вы сможете придумать сами так, чтобы это было логично. В том числе и в первой игре будет пересчет.



