Олимпиадная задача о минимизации автопарка семьи в Мехико по принципу Дирихле
Задача
а) В городе Мехико для ограничения транспортного потока для каждой частной автомашины устанавливаются два дня недели, в которые она не может выезжать на улицы города. Семье требуется каждый день иметь в распоряжении не менее десяти машин. Каким наименьшим количеством машин может обойтись семья, если её члены могут сами выбирать запрещенные дни для своих автомобилей? б) В Мехико для каждой частной автомашины устанавливается один день в неделю, в который она не может выезжать на улицы города. Состоятельная семья из десяти человек подкупила полицию, и для каждой машины они называют два дня, один из которых полиция выбирает в качестве невыездного дня. Какое наименьшее количество машин нужно купить семье, чтобы каждый день каждый член семьи мог самостоятельно ездить, если утверждение невыездных дней для автомобилей идёт последовательно?
Решение
а) 13 машин не хватит. Действительно, общее число запретов равно 26, в неделе 7 дней, поэтому в один из дней будут "отдыхать" не менее четырёх машин, то есть выехать смогут только 9.
14 машин достаточно: запретим четырём машинам понедельник и вторник, четырём – среду и четверг, двум – пятницу и субботу, двум – субботу и воскресенье, двум – пятницу и воскресенье. б) 11 машин не хватит: в один из дней недели будут "отдыхать" не менее двух машин.
Покажем, что 12 машин хватит. При подаче "заявления" на очередную машину семья будет указывать ту пару дней, в которые на данный момент есть запрет не более чем на одну машину. Так можно продолжать, пока не появятся 6 дней с двумя запретами, то есть так можно поступить для каждой из 12 машин. В результате в каждый день недели у семьи будет не более двух невыездных машин.
Ответ
а) 14; б) 12 машин.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь