Шахматный город
Город имеет форму квадрата, разделенного прямолинейными разрезами на района, как шахматная доска ( строк и столбцов). В городе осуществляется продажа дебютов. На рынке присутствуют покупателей и фирм-производителей, среди которых фирма «Королевский Гамбит». Цена на дебюты устанавливается государством на уровне у.е.
за штуку. Каждый потребитель хочет приобрести ровно дебютов. Фирмы не несут издержек производства. Каждый покупатель приобретает дебютов у фирмы, находящейся с ним в одном столбце или в одной строке. Если таких фирм несколько, покупатель приобретает дебюты поровну у каждой из фирм, расположенных с ним в одном столбце или в одной строке.
а) ( баллов) Фирма «Королевский Гамбит» распространяет вымышленную инсайдерскую информацию среди покупателей и других производителей. В результате она может выбрать все районы, в которых будут располагаться все потребители и производителей. Какую максимальную прибыль может получить фирма «Королевский Гамбит»?
Ответ
Так как фирмы не несут издержек производства, максимальная прибыль у всех фирм достигается при максимально возможном количестве проданных дебютов. Тогда приведем расстановку:
В данной расстановке фирма «Королевский Гамбит» — единственный продавец для всех покупателей, следовательно, достигается максимально возможная прибыль:
б) ( баллов) После раскрытия обмана, связанного с распространением ложной инсайдерской информации, потребители перестали доверять фирме «Королевский Гамбит» и стали самостоятельно выбирать районы своего расположения, а производителей вовсе покинули рынок из-за нулевой прибыли в прошлом периоде. Какую максимальную прибыль теперь может гарантировать себе фирма «Королевский Гамбит», если она принимает решение о выборе района для торговли после всех потребителей?
Ответ
Докажем, что фирма «Королевский Гамбит» всегда сможет выбрать район, чтобы продавать хотя бы двум потребителям: пусть два потребителя выбирают любые два района, тогда «Королевский Гамбит» может выбрать район на пересечении строки первого потребителя и столбца второго потребителя, а значит продавать хотя бы двум.
Теперь приведем расстановку, при которой максимальное число покупателей, которым мы продаем, равно :
Следовательно, максимальная гарантированная прибыль: .
в) ( баллов) Мэр города X решил устранить образовавшуюся монополию на рынке дебютов: он запретил фирме «Королевский Гамбит» продавать дебюты, решил привлечь производителей из соседнего региона и самостоятельно выбирать районы для их размещения. Какое наименьшее количество производителей ему необходимо привлечь, чтобы спрос каждого потребителя был удовлетворен независимо от расположения потребителей?
Ответ
Приведем расстановку, в которой минимальное необходимое число продавцов равно :
Теперь докажем, что для всех других расстановок достаточно четырех продавцов: в пункте б) мы уже доказали, что любым двум покупателям может продавать одна фирма, тогда, разбив покупателей на пары, мы получаем, что каждый продавец гарантированно сможет продать хотя бы одной паре, значит, четырех продавцов хватит на покупателей, независимо от их расстановки. Следовательно, минимальное необходимое число фирм равно .