|
25.06.01 11:00 |
Бензоколонки |
Условие
На кольцевой дороге расположено несколько бензоколонок, в каждой бензоколонке осталось некоторое количество бензина. Известно, что суммарное количество бензина во всех бензоколонках достаточно, чтобы автомобиль мог сделать полный круг. Докажите, что автомобиль с пустым баком (вместимость бака считаем неограниченной) может начать движение с некоторой бензоколонки и, заправляясь на встречающихся ему бензоколонках, сделать полный круг
Подсказка
Задачу можно переформулировать следующим образом: по окружности расставлено несколько чисел, сумма которых неотрицательна; нужно доказать, что можно найти одно из этих чисел, такое что оно само неотрицательно, его сумма со следующим неотрицательна, его сумма со следующими двумя неотрицательна, и т.д.
Решение
Решение 1: Фиксируем некоторое направление движения, скажем, по часовой стрелке. В дальнейшем слова "следующий" и "предыдущий" употребляем в смысле следующий и предыдущий относительно направления движения по часовой стрелке. Поставим в соответствие каждой бензоколонке число, равное разности между количеством бензина в этой бензоколонке и количеством бензина, которое требуется для проезда от этой бензоколонки до следующей (это число может быть как положительным, так и отрицательным). Тогда данную задачу можно переформулировать следующим образом: по окружности расставлено несколько (n) чисел, сумма которых неотрицательна (это условие эквивалентно тому, что бензина хватит, чтобы проехать полный круг); нужно доказать, что можно найти одно из этих чисел, такое что оно само неотрицательно, его сумма со следующим неотрицательна, его сумма со следующими двумя неотрицательна, и т.д., его сумма со следующими k числами неотрицательна (k пробегает натуральные числа от 1 до n-1). Выберем группу чисел, стоящих подряд по окружности, с максимальной суммой среди всевозможных групп чисел, стоящих по окружности подряд. Пусть эти числа -
a1,a2,... ,ak (считая по часовой стрелке), и за ними следуют числа ak+1,ak+2,...,an. Покажем, что число a1 - искомое. Рассмотрим сумму чисел a1+a2+...am, где m - некоторое натуральное число от 1 до n, и покажем, что эта сумма неотрицательна. Рассмотрим 2 случая. 1) Пусть m не превосходит k. Если предположить, что сумма a1+a2+...am отрицательна, то сумма am+1+am+2+...ak = (a1+a2+...ak)- (a1+a2+...am) будет больше, чем a1+a2+...ak, что противоречит выбору группы чисел a1,a2,...,am, как группы с максимальной суммой среди всевозможных групп подряд идущих чисел. 2) Пусть m>k. Если предположить, что сумма a1+a2+...am отрицательна, то сумма am+1+am+2+...an+a1+a2+...ak = (a1+a2+...an)+(a1+a2+...ak)- (a1+a2+...am) будет больше, чем a1+a2+...ak в противоречие с выбором группы чисел a1,a2,...,am. Решение 2:
Во-первых, ограничимся движением только по часовой стрелке, то есть докажем,
что есть бензоколонка, с которой можно проехать полный круг по часовой
стрелке. Проведем индукцию по числу бензоколонок.
Если бензоколонка одна - в ней достаточно бензина на полный
круг.
Пусть у нас есть N бензоколонок, N>1. Тогда можно найти 2 соседние
бензоколонки, такие, что из первой можно доехать до второй по часовой
стрелке. Это очевидно. Уберем вторую и отдадим весь ее бензин первой. По
индуктивному предположению, среди оставшихся N-1 существует одна, из которой
можно проехать полный круг по часовой стрелке. Легко показать, что с этой же
бензоколонки можно будет проехать полный круг и с N исходных бензоколонок.
МЦНМО
[все задачки]
|
![](/images/pic/fun.gif) Анекдот часа
|
Только в общаге Политеха вместо веревочки на смывном бачке можно увидеть…
>>>
[свежие]
последний: 10.01 10:02
всего анекдотов: 1255
[прислать свой]
|
|
|
![](/images/pic/quest.gif) ММЗадачка
|
|
|
|