Расселение
Алексей, Борис, Владимир и Георгий поступили в университет и получили право жить в общежитии. На данный момент в общежитии свободны как раз 4 места в 4 разных комнатах, в которых уже живут другие студенты. Ребята имеют различные предпочтения относительно соседей, с которыми они хотели бы жить, и потому различные предпочтения относительно четырех имеющихся мест. Информация о предпочтениях приведена в таблице. Студент Предпочтения Алексей $1 \succ 2 \succ 3 \ \succ 4$ Борис $1 \succ 3 \succ 4 \ \succ 2$ Владимир $3 \succ 1 \succ 2 \ \succ 4$ Георгий $4 \succ 1 \succ 2 \ \succ 3$ Запись $1 \succ 3 \succ 4 \ \succ 2$, например, означает, что для Бориса первая комната лучше, чем третья, та, в свою очередь, лучше, чем четвертая, и, наконец, четвертая лучше, чем вторая. Назовем распределение четверых ребят по комнатам неэффективным , если они могут поменяться комнатами так, чтобы никому не стало хуже и хотя бы одному из них стало лучше. В противном случае будем называть распределение эффективным .
Подпункты
а)
Является ли эффективным распределение $(\text{А}-2;\text{Б}-3;\text{В}-4;\text{Г}-1)$?
б)
Сколько всего существует эффективных распределений?
Решение
а) Это распределение не является эффективным, так как если Борис переедет в комнату 1, Владимир переедет в комнату 3, а Георгий — в комнату 4, то этим троим ребятам станет строго лучше, а Алексею будет не хуже (так как он останется в той же комнате). б) Проведем организованный перебор. 1) Алексей живет к комнате 4. Значит, Георгий — не в комнате 4. Следовательно, если Алексей и Георгий поменяются комнатами, им обоим станет лучше (а остальным будет не хуже). Значит, любое такое распределение неэффективно. 2) Алексей живет в комнате 3. Значит, Владимир живет не в комнате 3. Если он живет в комнатах 1 или 2, он может поменяться с Алексеем, и обоим станет лучше. Если он живет в комнате 4, он может поменяться с Георгием, и обоим станет лучше. Значит, любое распределение, при котором Алексей живет в комнате 3, неэффективно. 3) Алексей живет в комнате 2. Значит, остальные ребята занимают комнаты 1, 3 и 4. Заметим, что при распределении (Б – 1;В – 3;Г – 4) каждый из трех остальных ребят получает лучшую, со своей точки зрения, комнату. Поэтому распределение (А – 2;Б – 1;В – 3;Г – 4) эффективно, и, если Алексей живет в комнате 2, эффективно только это распределение. 4) Алексей живет в комнате 1. Нетрудно видеть, что распределения (А – 1; Б – 2; В – 3; Г – 4), (А – 1; Б – 3; В – 2; Г – 4) и (А – 1; Б – 4; В – 3; Г – 2) эффективны, а распределения (А – 1; Б – 3; В – 4; Г – 2), (А – 1; Б – 2; В – 4; Г – 3) и (А – 1; Б – 4; В – 2; Г – 3) — нет. Таким образом, существует 4 эффективных распределения. Ответ: а) Нет б) 4