Задача

В олимпиадах

Конкурс РЭШ — 2024

Баллы

25

Темы

Свойства

Сложность

0
Голосов еще нет

Автор

15.03.2024, 06:18 (Артём Липин)
15.03.2024, 06:18


(0)
Администратору спортивного лагеря нужно расселить чётное количество детей из первого отряда по комнатам. В каждой комнате могут жить ровно 2 человека. Все дети — девочки, поэтому изначально возможна любая пара потенциальных соседей. У каждого из детей есть предпочтения на множестве потенциальных соседей, то есть каждый из ребят может упорядочить всех потенциальных соседей от наилучшего для себя до наихудшего. При этом, для каждого из ребят эти предпочтения строгие — не существует двух соседей, которые были бы одинаково хороши с точки зрения кого-либо из ребят. Предпочтения также являются транзитивными, то есть если для девочки верно, что $i$ лучше $j$ (обозначим это утверждение как $i \succ j$) и $j \succ k$, то для неё верно $i \succ k$.

После того, как администратор расселил ребят по комнатам, ребятам можно меняться соседями. Для этого двое детей должны подойти к администратору и сказать, что они хотят жить друг с другом больше, чем со своими текущими соседями. Назовём стабильным такое расселение ребят, при котором никакая пара ребят не хочет подойти к администратору для совершения обмена.

Примечание. Задача является примером применения дизайна механизмов, о котором можно узнать больше из материалов просветительского проекта РЭШ GURU.

а) Пусть администратору надо расселить ровно 4 ребёнка. Сколько всего расселений возможны?

б) Может ли в этом случае быть ровно одно стабильное расселение? А два? А три? Если вы считаете, что может, приведите пример. Если нет, докажите невозможность.

в) Предположим, что администратору нужно расселить 6 детей. Для удобства занумеруем их от 1 до 6. Их предпочтения представлены в таблице ниже. Выражение $i \succ j$ означает, что, по мнению ребёнка, сосед $i$ лучше соседа $j$. Найдите все стабильные расселения и докажите, что других не существует.