Решите экономическую задачу пожалуйста

Question

Решите экономическую задачу пожалуйста

Иван Никитин Знаток (279), на голосовании 8 месяцев назад

Администратору спортивного лагеря нужно расселить чётное количество детей из первого отряда по комнатам. В каждой комнате могут жить ровно 2 человека. Все дети - девочки, поэтому изначально возможна любая пара потенциальных соседей. У каждого из детей есть предпочтения на множестве потенциальных соседей, то есть каждый из ребят может упорядочить всех потенциальных соседей от наилучшего для себя до наихудшего. При этом, для каждого из ребят эти предпочтения строгие — не существует двух соседей, которые были бы
одинаково хороши с точки зрения кого-либо из ребят. Если для ребёнка сосед і лучше соседа і, мы будем записывать это как і > j. Предпочтения также являются транзитивными, то есть если для девочки верно і > j и j > к, то для неё верно і > к. После того, как администратор расселил
ребят по комнатам, ребятам можно меняться соседями. Для этого двое детей должны подойти к администратору и сказать, что они хотят жить друг с другом больше, чем со своими текущими соседями.
Назовём стабильным такое расселение ребят, при котором никакая пара ребят не хочет подойти к администратору для совершения обмена.
а) Пусть администратору надо расселить ровно 4 ребёнка. Сколько всего расселений возможны? б) Может ли в этом случае быть ровно одно стабильное расселение? А два? А три? Если вы считаете, что может, приведите пример. Если нет, докажите невозможность. в) Предположим, что администратору нужно расселить б детей. Для удобства занумеруем их от 1
до 6. Их предпочтения представлены в таблице ниже. Выражение і > j означает, что, по мнению ребёнка, сосед і лучше соседа j. Найдите все стабильные расселения и докажите, что других не существует.

Дополнен 9 месяцев назад

Answer 1

Это классическая задача совпадения пар по предпочтениям, известная как проблема стабильного бракосочетания. Для решения этой задачи используется алгоритм Гейла-Шепли.

Для пункта а) найдем количество возможных расселений. В данном случае, есть всего 3 возможных варианта расселения 4 девочек по 2 в комнате: (1,2)(3,4), (1,3)(2,4), (1,4)(2,3).

Для пункта б) возможно одно стабильное расселение. Например, (1,2)(3,4).

Для пункта в) необходимо знать конкретные предпочтения, чтобы рассчитать все стабильные расселения. Если предоставить эти данные, я смогу помочь с решением. Также для более детального решения требуется составить таблицу предпочтений и использовать алгоритм Гейла-Шепли для нахождения всех стабильных расселений.