Олимпиадная задача Ященко на принцип Дирихле: минимум машин для семьи в Мексике
Задача
В Мексике экологи добились принятия закона, по которому каждый автомобиль хотя бы один день в неделю не должен ездить (владелец сообщает полиции номер автомобиля и "выходной" день недели этого автомобиля). В некоторой семье все взрослые желают ездить ежедневно (каждый – по своим делам!). Сколько автомобилей (как минимум) должно быть в семье, если взрослых в ней
а) 5 человек? б) 8 человек?
Решение
а) Пяти автомобилей не хватит, так как в день, когда один из автомобилей "отдыхает", кому-то не на чем будет ехать. Шести, очевидно, хватает. б) Если каждый день "отдыхает" не более одного автомобиля, то всего автомобилей не больше, чем дней недели, то есть семи. Но этого, очевидно, недостаточно. Значит, в какой-то день отдыхает два автомобиля, и в этот день нужно ещё как минимум 8 автомобилей. Итого 10. Мы доказали, что меньше, чем десятью автомобилями обойтись нельзя.
Десяти автомобилей достаточно: например, каждый рабочий день отдыхают по два автомобиля.
Ответ
а) 6; б) 10 автомобилей.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь