Как сделать вакцину дешёвой
В стране Акчурии имеется N городов, причём все города расположены вдоль единственной дороги. Правительство Акчурии собирается построить завод, в котором производится важная вакцина, которой нужно вакцинировать всех жителей Акчурии. Для перевозки вакцины с завода используется автотранспорт, при этом необходимо чтобы в каждый город было доставлено по две порции вакцины на каждого жителя. Перевозка одной вакцины на 1 километр обходится в 100 акчурийских драм. Стремясь сэкономить бюджетные средства, министерство здравоохранения Акчурии хочет разместить завод так, чтобы стоимость перевозки вакцины была минимальной.
1) Постройте график, иллюстрирующий задачу.
2) Определите (и обоснуйте), где следует построить завод, если N не больше 4, а количество жителей в каждом из городов равно 100 тысячам человек, причем в каждый город должна ехать отдельная машина.
3) Определите (и обоснуйте), где следует построить завод при любом N, если количество жителей в каждом из городов равно 100 тысячам человек, причем в каждый город должна ехать отдельная машина.
4) Определите (и обоснуйте), где следует построить завод, если количество городов в Акчурии чётное и в «первой» половине городов, считая от начала страны, проживает по 100 тысяч человек, а во «второй» половине – по 200 тысяч человек, причем в каждый город должна ехать отдельная машина
1) (2 балла). Варианты рисунка, принимавшиеся как верные. Главное: на рисунке не должно быть очевидным, что города расположены на одном расстоянии и что завод расположен в середине (так как это первое явно не следовало из условия, а второе неверно для нечетного количества городов). Например, должно было быть подписано, что завод может быть в любом месте, а расстояние между городами – произвольное. Участники, верно строившие график зависимости стоимости перевозки от расстояния (функции y = 100x), также получали 2 балла.
или
2. Способ 1 (решение с помощью полного перебора вариантов) а) Если город один, выгоднее всего ставить завод там же, где и город. Тогда расстояние будет 0 (1 балл) б) (1 балл) Если городов два, нужно ставить завод в любом между ними, в том числе в любом из городов, так как сумма расстояний равна длине отрезка АВ (АС + ВС = АВ)
При этом, если завод будет с одной стороны от обоих городов (например, слева), расстояние будет равно CA+AB, что больше AB
в) (2 балла) Если городов три, то поставив завод в центральном городе (городе С), можно получить сумму расстояний равную AB = AC + BC + 0 (см б). Меньше получить невозможно т.к. в предыдущем пункте было доказано, что для двух городов расстояние не меньше AB.
г) (2 балла) Если городов четыре, рассмотрим пары городов AD и BC. Для случая с двумя городами было доказано, что минимальное расстояние от завода до двух любых городов, между которыми он размещён, равно расстоянию между этими городами. Тогда разбив города на пары можно получить, что сумма длин дорог равна сумме отрезков AD и BC (иначе говоря, завод должен быть расположен в любой точке между городами А и D, если рассматривать только их, и в любой точке между городами B и С, если рассматривать только их. Так как BC принадлежит AD, нужно разместить завод в любой точке на отрезке ВС. Итак, если построить завод между городами B и C или в них самих, сумма расстояний,будет равна (AE + ED) + (BE + EC) = AD + BC
Верное решение в общем виде (см. пункт 3)
3) (8 баллов)
Пусть городов чётное количество. Тогда докажем разными способами, что оптимально ставить между двумя центральными.
Оценка + пример:
Разобьём города на пары [A_1, A_n], [A_2, A_{n-1}] \ldots. Сумма дорог от завода до 2-х городов в одной паре не меньше, чем расстояние между ними. Значит сумма расстояний от завода до городов не может быть меньше, чем A_1A_n + A_2A_{n-1} + \ldots + A_{n/2}A_{n/2 + 1}. Если ставить завод между A_{n/2} и A_{n/2 + 1}, сумма расстояний будет иметь именно такой
по индукции:
Докажем, что лучше всего ставить завод между двумя центральными городами. Для n=2 это доказано в предыдущем пункте задачи.
Для n по предположению индукции город стоит где-то между A_{n/2 - 1} и A_{n/2 + 2}. Теперь у нас ситуация, когда нужно располагать завод относительно двух оставшихся, и мы делаем это по такому же принципу (для n=4 доказано в предыдущем пункте задачи).
4) (10 баллов). Рассмотрим каждый город, в котором было 200 тысяч людей как 2 города по 100 человек. Тогда у нас не n городов, а 3n/2 городов и если 3n/2 не кратно двум, ставим в центральном городе (то есть (3n/2 + 1)/2 = (3+n)/4. Иначе, если 3n/2 чётно, то между центральными (то есть между 3n/4 и 3n/4 + 1 ). Первые n/2 городов считаются за один каждый, а остальные города – за 2 (так мы перевели города с 200000 населением в 2 города с населением 100000 жителей).
Тогда переводы обратно: в случае нечётного кол-ва ((3n + 2)/4 - n/2)=(n + 2)/4 – город начальная с которого идут по 200к жителей. Далее каждый второй город у нас идёт как новый. Значит ответ – город с номером (n + 2)/4 / 2 + n/2, где // – это целочисленное деление (сокращая получаем (5n + 10)/8.
Если количество городов чётное (что и рассмотрено в условии) же чётное: завод необходимо разместить между городами 3n/4 и 3n/4 + 1. Это n/4\ и n/4 + 1 считает от середины. Перевод в изначальную нумерацию городов, укажем, что это города с номерами n/4/2 + n/2/2 = (5n + 4)/8.