Задачки

Условие

На кольцевой дороге расположено несколько бензоколонок, в каждой бензоколонке осталось некоторое количество бензина. Известно, что суммарное количество бензина во всех бензоколонках достаточно, чтобы автомобиль мог сделать полный круг. Докажите, что автомобиль с пустым баком (вместимость бака считаем неограниченной) может начать движение с некоторой бензоколонки и, заправляясь на встречающихся ему бензоколонках, сделать полный круг

Подсказка

Задачу можно переформулировать следующим образом: по окружности расставлено несколько чисел, сумма которых неотрицательна; нужно доказать, что можно найти одно из этих чисел, такое что оно само неотрицательно, его сумма со следующим неотрицательна, его сумма со следующими двумя неотрицательна, и т.д.

Решение

Решение 1:
Фиксируем некоторое направление движения, скажем, по часовой стрелке. В дальнейшем слова "следующий" и "предыдущий" употребляем в смысле следующий и предыдущий относительно направления движения по часовой стрелке. Поставим в соответствие каждой бензоколонке число, равное разности между количеством бензина в этой бензоколонке и количеством бензина, которое требуется для проезда от этой бензоколонки до следующей (это число может быть как положительным, так и отрицательным). Тогда данную задачу можно переформулировать следующим образом: по окружности расставлено несколько (n) чисел, сумма которых неотрицательна (это условие эквивалентно тому, что бензина хватит, чтобы проехать полный круг); нужно доказать, что можно найти одно из этих чисел, такое что оно само неотрицательно, его сумма со следующим неотрицательна, его сумма со следующими двумя неотрицательна, и т.д., его сумма со следующими k числами неотрицательна (k пробегает натуральные числа от 1 до n-1). Выберем группу чисел, стоящих подряд по окружности, с максимальной суммой среди всевозможных групп чисел, стоящих по окружности подряд. Пусть эти числа - a₁,a₂,... ,a_k (считая по часовой стрелке), и за ними следуют числа a_k+1,a_k+2,...,a_n. Покажем, что число a₁ - искомое. Рассмотрим сумму чисел a₁+a₂+...a_m, где m - некоторое натуральное число от 1 до n, и покажем, что эта сумма неотрицательна. Рассмотрим 2 случая. 1) Пусть m не превосходит k. Если предположить, что сумма a₁+a₂+...a_m отрицательна, то сумма a_m+1+a_m+2+...a_k = (a₁+a₂+...a_k)- (a₁+a₂+...a_m) будет больше, чем a₁+a₂+...a_k, что противоречит выбору группы чисел a₁,a₂,...,a_m, как группы с максимальной суммой среди всевозможных групп подряд идущих чисел. 2) Пусть m>k. Если предположить, что сумма a₁+a₂+...a_m отрицательна, то сумма a_m+1+a_m+2+...a_n+a₁+a₂+...a_k = (a₁+a₂+...a_n)+(a₁+a₂+...a_k)- (a₁+a₂+...a_m) будет больше, чем a₁+a₂+...a_k в противоречие с выбором группы чисел a₁,a₂,...,a_m.
Решение 2:
Во-первых, ограничимся движением только по часовой стрелке, то есть докажем, что есть бензоколонка, с которой можно проехать полный круг по часовой стрелке. Проведем индукцию по числу бензоколонок. Если бензоколонка одна - в ней достаточно бензина на полный круг. Пусть у нас есть N бензоколонок, N>1. Тогда можно найти 2 соседние бензоколонки, такие, что из первой можно доехать до второй по часовой стрелке. Это очевидно. Уберем вторую и отдадим весь ее бензин первой. По индуктивному предположению, среди оставшихся N-1 существует одна, из которой можно проехать полный круг по часовой стрелке. Легко показать, что с этой же бензоколонки можно будет проехать полный круг и с N исходных бензоколонок.

МЦНМО