Школа №179 из 8 в 9 класс 2022 год

Школа № 179

2022 год

26.03.2022

1. Придумайте компанию из нескольких мужчин и такого же количества женщин с такими предпочтениями, что существует как минимум два стабильных способа поженить их всех.
   
   
2. 1. a) Докажите, что процесс выполнения алгоритма капитана когда-нибудь закончится, то есть он не может продолжаться вечно.
   2. б) Докажите, что в ситуации корабля «Земля – Андромеда» (описанной в статье) на этот процесс не может уйти больше 20 лет.
   
   
   
3. Докажите, что алгоритм, предложенный капитаном, обязательно приведёт к некоторому стабильному способу женитьбы всего экспедиционного корпуса.
   
   
4. Письменно сформулируйте, в чём состоит описанная в статье задача и какое решение предложил капитан.
   
   
5. 1. a) На картинке на обороте проведите несколько отрезков с концами в данных точках так, чтобы:
      • каждая точка была концом ровно для одного отрезка;
      • концы каждого отрезка были разного цвета;
      • если любой из проведённых отрезков стереть и соединить его конец с любой другой точкой противоположного цвета, то новый отрезок будет длиннее стёртого или длиннее того отрезка, концом которого является эта точка.
   2. б) Пусть на плоскости дано несколько точек двух цветов, поровну каждого цвета, причём все расстояния между точками различны. Докажите, что тогда способ проведения отрезков, описанный в пункте (а), существует и единственен.
   
   
   
6. Допустим, что все члены экспедиции, описанной в статье, кроме одной коварной женщины, действуют по изложенным капитаном правилам. А эта коварная женщина, получая письма, каждый раз отказывает всем кроме одного, но тому, кому она не отказала, может (по её желанию) не быть лучшим среди написавших ей. Может ли коварная женщина в результате получить себе лучшего мужа, чем если бы вела себя по правилам?

Решения задач

1. Пример компании с двумя стабильными распределениями:
   Пусть есть мужчина А и мужчина Б; женщина 1 и женщина 2.
   Предпочтения:
   Мужчины: А предпочитает 1 > 2; Б предпочитает 2 > 1
   Женщины: 1 предпочитает Б > А; 2 предпочитает А > Б
   Стабильные распределения: 1. (А-1), (Б-2) 2. (А-2), (Б-1) Ответ: См. пример выше.
2. 1. a) Каждое предложение мужчины уменьшает список доступных женщин. Так как мужчины делают не более $n$ предложений каждым, а женщин $n$, общее число шагов не превысит $n^2$.
   2. б) При количестве членов экипажа ≤10 пар максимальное число дней процесса будет $10 \cdot 2 - 1 = 19$ дней ⇒ уложится в 20 лет. Ответ: Число предложений ограничено $\frac{n(n+1)}{2}$, при $n = 10$ ⇒ ≤55 дней.
3. Алгоритм капитана реализует мужской алгоритм Гейла-Шепли. Он гарантирует стабильность, так как каждый мужчина последовательно делает предложения, а женщины выбирают лучшего из доступных кандидатов. Теоретически доказывается отсутстьие блокирующих пар.
4. Задача: распределить мужчин и женщин в стабильные браки без взаимных предпочтений. Решение: последовательные предложения мужчин с учетом рангов предпочтений и временных отказов женщин.
5. 1. a) Решение: Соединить точки по принципу минимальной суммарной длины пар с чередованием цветов. Жадное сопоставление гарантирует невозможность улучшения.
   2. б) Единственный способ — построить пары, где каждый отрезок является минимально возможным среди допустимых вариантов. Единственность следует из упорядочения всех расстояний. Ответ: Строим пары последовательно выбирая минимальное незанятое расстояние между разноцветными точками.
6. Да, может. Если коварная женщина отказывает промежуточным кандидатам, она может заставить оптимального для нее мужчину остаться доступным дольше. Пример: женский алгоритм дает ей оптимально-стабильный брак, а отклонения могут привести к улучшению. Ответ: Возможно путём стратегических отказов.