Показать скрытый текст Для N=1 утверждение очевидно. Пусть оно справедливо, например, для N=100. Докажем его для N=100+1. Существует хотя бы одна бочка(например бочка 5), которой хватит для того чтобы доехать до следующей бочки(бочки 6). Если не так, то суммы бензина всех бочек не хватит - противоречие с условием задачи. Доедем от бочки 5 до бочки 6, остаток бензина перельём в бочку 6, получим случай 100.
Утверждение доказано.
Вы доказали обратное.
Вы доказали, что если если есть 100 бочек с общим кол-вом бензина 100 л, разбросанных и разлитых так, что найдётся такая, с которой можно начать путешествие по кругу и проехать полный круг, то всегда можно добавить ещё одну бочку и переразлить бензин так, что можно было пройти круг с э.той же бочки.
А требуется доказать обратное, т.е. как бы мы не переразливали бы бензин по бочкам, всегда можно найти бочку, начсиная с которой можно проехать круг.
Вы не так поняли моё доказательство. Вероятно, надо было обьяснить подробнее. Сейчас попробую.
Для начала строго сформулируем доказываемое утверждение:
Для любого натурального N (количество бочек), если суммарное количество горючего (в литрах) равно
длине дороги (в километрах), то можно обьехать всю дорогу , двигаясь (для определённости) по часовой стрелке.
Воспользуемся методом математической индукции.Для N=1 утверждение очевидно (база индукции).Предположим что утверждение доказано для какого-то N. Докажем его для N+1. (переход индукции).
Пусть, например, на рисунке А N=6, N+1=7.
1. Найдётся хотя бы одна бочка, бензина в которой хватит чтобы доехать до следующей бочки (двигаясь по часовой стрелке). Если предположить противное (то что во всех бочках бензина не хватает), то и суммы ёмкостей всех бочек не хватит для всего маршрута, а это не так (у нас есть 7 л на 7 км).
То есть Б1,Б2,Б3,Б4,Б5,Б6,Б7 - количества бензина в бочках (в литрах), Д1,Д2,Д3,Д4,Д5,Д6,Д7 - длины участков, соответственно, 1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-1.
Предположим что Б1 < Д1, Б2 < Д2, Б3 < Д3, Б4 < Д4, Б5 < Д5, Б6 < Д6, Б7 < Д7.
Тогда и Б1 + Б2 + Б3 + Б4 + Б5 + Б6 + Б7 < Д1 + Д2 + Д3 + Д4 + Д5 + Д6 + Д7 - противоречие с условием задачи (количество горючего не меньше чем длина дороги). Значит, найдётся хотя бы одна бочка, для которой Б >= Д.
2. Пусть, например, эта "большая" бочка - бочка 4 (рисунок А). Постараемся перейти к предыдущему, уже доказанному случаю (N=6). Проделаем следующую процедуру: временно "вырежем" из нашего пути целиком участок 4-5 вместе с бочкой 4. Теперь за точкой 3 будет сразу следовать точка 5 (рисунок Б).
3.Дальше, в бочке 4 оставим бензина ровно столько, чтобы хватило на проезд по участку 4-5 (временно удалённому), а излишки (если они есть) на время перельём в бочку 5.
//текст доступен после регистрации//4. Если внимательно посмотреть на рисунок Б, то он удовлетворяет всем условиям доказываемого утверждения для Н=6, т.е суммарного бензина в бочках 1,2,3,5,6,7 хватит для проезда по пути 1-2-3-5-6-7 (по условию его хватало раньше, и мы убрали бензина с бочкой 4 столько литров, сколько километров в удалённом участке 4-5). Значит, по предположению индукции, существует некоторый маршрут по которому можно обьехать наши 6 участков (двигаясь по часовой стрелке). Пусть, например, это будет маршрут 2-3-5-6-7-1-2.
5.Теперь осторожно вернём на своё место удалённый участок 4-5 (который зелёного цвета) вместе с бочкой 4.
Теперь маршрут 2-3-5-6-7-1-2 превращается в маршрут 2-3-
4-5-6-7-1-2.
6. Проверим, хватит ли у нас бензина для движения по этому новому маршруру. Едем по участку 2-3. Проежаем отрезок 3-5 (коричневый пунктир), но теперь вместо точки 5 мы попадаем в точку 4. В точке 4 стоит возвращённая бочка 4. Если помните, бензина в ней оставалось ровно столько чтобы проехать участок 4-5. Значит, доежаем до бочки 5, а дальше всё как было в маршруте 2-3-5-6-7-1-2.
7. Осталось только вернуть в бочку 4 тот излишек бензина, который перед удалением участка 4-5 мы перелили в бочку 5. Легко видеть что на "проходимость" маршрута это не повлияет: излишек, который прежде находился в бочке 5, теперь мы нетронутым доставляем по участку 4-5, то есть, по сути, ничего не изменилось.
8. (добавлено) В случае, когда маршрут для N=6 начинается с бочки номер 5 (то есть следующей за удалённой бочкой 4) следует уточнить что искомый маршрут для N=7 начинается не с бочки 5, а с бочки 4. То есть не 5-6-7-1-2-3-4-5, а 4-5-6-7-1-2-3-4. После возврата "одолженного" бензина бензина в бочке 5 может не хватить, но если начать с бочки 4, то "одолженный" бензин доставляется в бочку 5 , и дальше всё идёт как по маслу! Таким образом, предположив существование требуемого маршрута для N=6, мы доказали существование маршрута для N=7. Если получилось запутанно, можно самим повторить рассуждение для случая N=2 (это легко), потом для N=3.
