Оптимальное расселение

б) Занумеруем детей от 1 до 4. Тогда все расселения условно обозначим 12, 13 и 14 — по тому, с кем живёт первый ребёнок. Для каждого примера создадим таблицу, иллюстрирующую его.

Начнём с единственного стабильного расселения. В примере ниже можно быстро показать, что единственное стабильное расселение это 12. Каждый из соседей в расселении 12 живёт с лучшим для себя, поэтому не хочет меняться. При этом в расселениях 13 и 14 захочет поменяться, например, пара (1, 2).

Приведём пример с двумя стабильными расселениями. В этом случае стабильные распределения — это 12 и 14. Заметим, что в расселении 12 есть два ребёнка (1 и 3), которые живут с лучшим для себя соседом, поэтому не будут меняться. Тогда поменяться могут только 2 и 4, но они худшие варианты друг для друга, поэтому меняться не будут. Аналогично, в расселении 14 есть два ребёнка (2 и 4), которые живут с лучшим для себя соседом, поэтому не будут меняться. Тогда поменяться могут 1 и 3, но они худшие варианты друг для друга, поэтому меняться не будут. Расселение 13 не будет стабильным, поскольку захотят поменяться, например, 1 и 2.

Теперь докажем, что не может быть трёх стабильных распределений. Заметим, что если два человека живут с худшими для себя соседями, то они хотели бы поменяться с кем угодно. Также заметим, что если два человека — лучшие соседи друг для друга, то любое распределение, где они не живут вместе, не может быть стабильным.
Всего есть 3 расселения и 4 человека. Значит, есть хотя бы одно расселение, где сразу 2 человека живут с худшим для себя соседом. Любители комбинаторики могут вспомнить принцип Дирихле.
Если они живут не друг с другом, то они могут поменяться, значит, расселение не стабильно. Если же они живут друг с другом, то один из них может поменяться с кем-то в другой паре, если эта пара не является лучшими соседями друг для друга. Если хотя бы для одного из оставшейся пары сосед не лучший, то он согласится поменяться с кем-то из худших друг для друга соседей, поэтому такое расселение не будет стабильным.
Остался последний случай, при котором эта пара — лучшие друг для друга соседи. Тогда они всегда живут друг с другом в стабильном расселении, значит, остальные расселения не стабильны. Таким образом, 3 стабильных расселения невозможны

в) Рассмотрим предпочтения, описанные в условии.

Шаг 1. Рассмотрим решение индивида i. Если для индивида j он является лучшим соседом, то индивид i не выберет в стабильном расселении никого хуже с его точки зрения, чем j, потому что всегда можно решить жить с j. Учитывая это, вычеркнем невозможные пары. На картинке ниже красным зачёркнуты невозможные пары. Затем те же пары зачёркнуты оранжевым (каждая пара встречается дважды).

Шаг 2. Заметим, что из оставшихся возможных опций 5 и 6 — лучшие друг для друга (обведено зелёным на картинке). Значит, они будут жить вместе. Тогда зачеркнём зелёным невозможные пары из числа оставшихся.

Шаг 3. Остаётся заметить, что возможны два стабильных расселения оставшихся —13 24 и 14 23. В первом случае 1 и 2 живут с лучшими для себя соседями, а 3 и 4 не готовы меняться. Во втором случае 3 и 4 живут с лучшими для себя соседями, а 1 и 2 не готовы меняться.

Ответ. Всего 2 стабильных расселения —13 24 56 и 14 23 56.