2014-06-08
На кольцевой дороге расположены $n$ заправочных станций, содержащие вместе такое количество бензина, которого хватает для поездки одного автомобиля по всему кругу ровно один раз. Доказать, что автомобиль с пустым баком (неограниченной вместимости) может начать движение с одной из заправочных станций (предварительно заправившись на ней) и совершить полную поездку по кругу.
Решение:
Предположим, что машина имеет запас бензина, достаточный для того, чтобы проехать всю дорогу без заправок. Пусть она начинает движение с любой станции (забирая по дороге весь бензин на каждой станции) и оканчивает движение в той же точке и с тем же количеством бензина. Обозначим через А станцию, подьезжая к которой, машина имела в баке наименьшее за все время движения количество бензина. Пусть в этот момент количество бензина в машине было равным х. Если машина с количеством бензина, равным х, начнет движение со станции А. то в баке всегда будет бензина не меньше х. Следовательно, если машину с пустым баком заправить на станции A, то она сможет, начиная движение с этой станции, совершить поездку по кругу (так как это количество х бензина можно с самого начала вылить и совершить путешествие без него).