Расселение

Задача

Московская олимпиада школьников — 2015

Заключительный этап: первый день 10-11 классы

микроэкономика

теория игр

Средняя: 3 (2 оценок)

Алексей Суздальцев

21.02.2015, 20:04 (Данил Фёдоровых)
30.07.2015, 12:40

(3)

Версия для печати

Только условие

Условие с решением и ответом

Только решение и ответ

Алексей, Борис, Владимир и Георгий поступили в университет и получили право жить в общежитии. На данный момент в общежитии свободны как раз 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

Все задачи этой олимпиады

Заключительный этап: второй день 10-11 классы

Задача	Баллы
Всё по P рублей!	20
Дилемма центробанка	20
Магазины в Кукумбрии	20
Перераспределение доходов спортивных клубов	20
Фирма, самолет, менеджер	20

Заключительный этап: второй день 8-9 классы

Задача	Баллы
Билеты на футбол	20
Гаджет и Микросхемов	20
ЛДН	20
Магазины в Кукумбрии	20
Рассрочка	20

Заключительный этап: первый день 10-11 классы

Задача	Баллы
Вклад Марьи	5
Два ковбоя	5
Двойной пирог	5
Девяносто девять цен	5
Расселение	20
Рейтинги	20
Спринтеры	20
Типичные пингвины	20

Заключительный этап: первый день 8-9 классы

Задача	Баллы
Вклад Ивана	5
Господин Гаджет	5
Два ковбоя	5
Дели и выбирай	5
Импортозамещение	21
Тугрики и еврики	15
Филолог Сергей	21
Франчайзинг	23

В олимпиадах

Раздел

Баллы

Темы

Сложность

Автор

Все задачи этой олимпиады