Авто 2

[Miki]

сумма излишек всегда будет равнятся сумме недостач,теперь допустим есть несколько излишек и несколь недостач,как доказать что среди этих излишек есть та бочка которая сделает полный оборот?

[Michael]

Miki, посмотрите на график поста 37, вы с ним согласны? Если нет, то в чём именно?

[buka]

э

Buka спасибо,действительно надо начинать с указанной бочки,но как доказать что такая бочка в любом случае должна быть логически?

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 (рисунок А). ...

Мики, вы про это спрашивали? Или вы хотите именно график?

этим доказывается что, даже если во всех будет недостача найдется бочка с излишком,которая и будет бочкой с которой можно сделать полный оборот

Когда во всех бочках недостача и лишь в одной - избыток, это простой случай.
Но когда есть несколько бочек с избытком, далеко не любая с избытком подойдёт.

[Miki]

э

Buka спасибо,действительно надо начинать с указанной бочки,но как доказать что такая бочка в любом случае должна быть логически?

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 (рисунок А). ...

Мики, вы про это спрашивали? Или вы хотите именно график?

этим доказывается что, даже если во всех будет недостача найдется бочка с излишком,которая и будет бочкой с которой можно сделать полный оборот

Когда во всех бочках недостача и лишь в одной - избыток, это простой случай.
Но когда есть несколько бочек с избытком, далеко не любая с избытком подойдёт.

да да,вот я и говорю по крайней мере одна будет с излишком,но если несколько с излишком,как можно логически словами доказать,что и среди них найдется такая бочка

[Miki]

вы находите эту бочку,я с вами согласен,но как доказать что эта бочка в любом случае должна быть?

[Miki]

надо анализировать бочки с излишками так как с них начинается путь и доказать что среди них в любом случае есть бочка которая сделает полный оборот

[Валерий]

Если грубо, то похоже на принцип перетекающих сосудов, из одного вытекает в другой втекает

[buka]

Buka спасибо,действительно надо начинать с указанной бочки,но как доказать что такая бочка в любом случае должна быть логически?

Мне трудно понять и почувствовать, что Вам не нравится...
Хорошо, я постараюсь немного по-другому изложить ход рассуждения.
У нас есть М бочек В1,...,БК,...,БР,...,БС,...,БМ.
Допустим, мы начнём путь с Б1, проедем некоторое расстояние, но до бочки БК не сможем доехать Х1 км. Это значит, что на участке Б1-БК есть дефицит в Х1 литров (при расходе 1 л/км расстояние можно выражать в литрах и расход в километрах ).
Но это же значит, что на участке БК-Б1 есть избыток в те же Х1 литров,
Значит с Б1 в этом направлении начинать нельзя. Легко показать, что нельзя начинать и с любой бочки между Б1 и БК: если мы начнём с бочки БА, которая где-то между Б1 и БК, то мы с неё не доедем до БК (ведь начиная с Б1 мы подъехали к БА либо с пустым баком (в крайнем случае), либо в баке было немного бензина. А если мы начнём с БА, то начнём с пустого бака).
Итак, мы убедились, что с бочек Б1,...,БК-1 начинать нельзя.
Начнём с бочки БК, зная что на участке БК-Б1 есть избыток в Х1 литров.
Допустим, что мы опять не смогли доехать до какой-то бочки БР Х2 километров.
Что это значит? Это значит, что общий дефицит на участке Б1-БР = Х1+Х2 литров, и общий избыток на участке БР-Б1 = тоже Х1+Х2 литров.
Начнём с бочки БР... И так далее. Допустим, что мы много раз так вот лажались и в конце концов последний раз не сумели доехать до бочки БС ХС километров.
Значит общий дефицит у нас от Б1 до БС = Х1+Х2+...+ХС литров, что автоматически значит что у нас избыток в Х1+Х2+...+ХС литров на учаске БС-Б1.
Что значит избыток? Это значит, что общее кол-во бензина на участке БС-Б1 равно тому, что необходимо проехать от БС до Б1 плюс этот избыток в Х1+Х2+...+ХС.
Теперь, если БС - это последняя наша неудачная бочка (ну должно же когда-то кончиться это невезение ), то начав с БС мы доедем до Б1 и при этом у нас останется в Баке Х1+Х2+...+ХС литров! Значит, начав с самого начала с БС, а не с Б1 мы бы объехали круг.

[Redirect]

бука, вы отдыхаете когда-нибудь ?)

[Miki]

Buka спасибо,действительно надо начинать с указанной бочки,но как доказать что такая бочка в любом случае должна быть логически?

Мне трудно понять и почувствовать, что Вам не нравится...
Хорошо, я постараюсь немного по-другому изложить ход рассуждения.
У нас есть М бочек В1,...,БК,...,БР,...,БС,...,БМ.
Допустим, мы начнём путь с Б1, проедем некоторое расстояние, но до бочки БК не сможем доехать Х1 км. Это значит, что на участке Б1-БК есть дефицит в Х1 литров (при расходе 1 л/км расстояние можно выражать в литрах и расход в километрах ).
Но это же значит, что на участке БК-Б1 есть избыток в те же Х1 литров,
Значит с Б1 в этом направлении начинать нельзя. Легко показать, что нельзя начинать и с любой бочки между Б1 и БК: если мы начнём с бочки БА, которая где-то между Б1 и БК, то мы с неё не доедем до БК (ведь начиная с Б1 мы подъехали к БА либо с пустым баком (в крайнем случае), либо в баке было немного бензина. А если мы начнём с БА, то начнём с пустого бака).
Итак, мы убедились, что с бочек Б1,...,БК-1 начинать нельзя.
Начнём с бочки БК, зная что на участке БК-Б1 есть избыток в Х1 литров.
Допустим, что мы опять не смогли доехать до какой-то бочки БР Х2 километров.
Что это значит? Это значит, что общий дефицит на участке Б1-БР = Х1+Х2 литров, и общий избыток на участке БР-Б1 = тоже Х1+Х2 литров.
Начнём с бочки БР... И так далее. Допустим, что мы много раз так вот лажались и в конце концов последний раз не сумели доехать до бочки БС ХС километров.
Значит общий дефицит у нас от Б1 до БС = Х1+Х2+...+ХС литров, что автоматически значит что у нас избыток в Х1+Х2+...+ХС литров на учаске БС-Б1.
Что значит избыток? Это значит, что общее кол-во бензина на участке БС-Б1 равно тому, что необходимо проехать от БС до Б1 плюс этот избыток в Х1+Х2+...+ХС.
Теперь, если БС - это последняя наша неудачная бочка (ну должно же когда-то кончиться это невезение ), то начав с БС мы доедем до Б1 и при этом у нас останется в Баке Х1+Х2+...+ХС литров! Значит, начав с самого начала с БС, а не с Б1 мы бы объехали круг.

я не говорю что мне не нравится, но надо вам послать решение на braingames.ru чтобы точно быть уверенным

[Miki]

может я ошибаюсь и не утверждаю, но я думаю что можно доказать на основе предельных положений что можно сделать полный оборот и что существует такая бочка: допустим у нас N бочек,исходя из того что что количество бензина в N бочках должно быть 100л, можно доказать что даже если в N-1 бочках недостача в бочке m=1 будет излишек, который позволит сделать оборот,так как сумма недостач=сумме излишек, теперь будем анализировать бочки с излишками, допустим m=2, то есть есть 2 бочки с излишками, опять же если даже в одной бочке с излишком недостаточно чтобы добраться до другой бочки с излишком, а добраться это значит потом сделать полный оборот,то во второй обязательно будет такой излишек чтобы добраться до первой бочки с излишком, если так продолжать с 3, 4, 5..........,бочками с излишками,то это значит всегда есть такая бочка с излишком ,которая позволит сделать полный оборот!

[Smith]

док-во:
максимальное кратчайшее расстояние между n бочками при любом расположении бочек является пропорциональным и не превышает 100/n км, а минимальное пропорциональное распределение бензина между n бочками составляет также 100/n л. следовательно, всегда найдется путь, который, обеспечит безболезненное продвижение и дозаправку автомобиля на всем пути следования, ч.т.д.

слегка подправил цитату, и получилось вот что:
док-во:
максимальное из возможных кратчайших расстояний между n бочками получается при их равномерном расположении по всей длине пути, и не превышает 100/n км, а минимальное из возможных максимальных наполнений бочек бензином возникает также при равномерном распределении бензина между n бочками и составляет также 100/n л. следовательно, всегда найдется хотя бы одна бочка, начав с которой автомобиль сможет преодолеть как минимум одно расстояние до бочки слева или справа без дозаправки.
аналогично доказывается, что существует хотя бы одно направление следования автомобиля, при котором он сможет доехать хотя бы до одной следующей бочки, и т.д.
т.о, при правильном выборе отправной точки и направления следования, автомобиль сможет преодолеть весь путь, ч.т.д.
 

[Smith]

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

[Smith]

Мики, ау, блин! 

[Miki]

Здравствуй дружище Смит, у Buki доказательство сильное, мое под большим вопросом