Задача

В олимпиадах

Заключительный этап ВОШ - 2018

Раздел

Баллы

6

Сложность

9
Средняя: 9 (1 оценка)
29.04.2018, 21:37 (Алёна Захарова)
29.04.2018, 21:37


(0)
В стране A есть четыре города и прямые дороги между ними. Расположение городов и дорог, а также расстояния между городами изображены на картинке. В скобках указано население городов в миллионах человек.

Государство думает, где именно расположить мусорную свалку. Для возможности транспортировки мусора свалка может находиться только непосредственно на обочине дороги или в самих городах. Конечно, жители каждого города хотят, чтобы свалка была как можно дальше от их города (для простоты будем считать, что они имеют в виду расстояние, которое нужно проехать по дороге).
а) (2 балла) Назовем точку X доминирующим местом для свалки, если она победила бы во всеобщем голосовании жителей страны, будучи выставленной против любой другой точки, по правилу простого большинства голосов. При правиле простого большинства побеждает тот вариант расположения, который получает строго больше половины голосов всех жителей. При безразличии жителей города между двумя вариантами считайте, что они разделяют свои голоса поровну между предлагаемыми вариантами.
Есть ли в стране A доминирующее место для свалки? Если есть, найдите его; иначе докажите, что его нет.
б) (3 балла) Назовем точку Y неудачным местом для свалки, если существует такая точка Z, что жители по меньшей мере трех городов строго предпочитают точку Z точке Y. Найдите множество неудачных мест для свалки.
г) (1 балл) Глава государства Джон Ролз решил разместить свалку таким образом, чтобы ни один город не был особенно ущемлен: решение принимается так, чтобы свалка была как можно дальше от ближайшего к ней города. Где будет размещена свалка?