Задача

В олимпиадах

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

Раздел

Баллы

20

Темы

Сложность

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

Автор

21.02.2015, 20:04 (Данил Фёдоровых)
30.07.2015, 12:40
Алексей, Борис, Владимир и Георгий поступили в университет и получили право жить в общежитии. На данный момент в общежитии свободны как раз 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)$?
б) Сколько всего существует эффективных распределений?

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

Заключительный этап: второй день 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