Авто 2

[Smith]

та это всё классно, а моё???

[Miki]

Смит не могу сказать, надо все решения послать на Braingames, может у них совсем другое решение-не согласятся

[Michael]

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

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

Не, Смит, если бы было так просто, то я бы не мучался и не рисовал график. Я согласен с первой частью Вашего рассуждения, что можно найти эту первую бочку. Хопрошо, он доехал до следующей бочки, а дальше? Первую бочку он выбирал, а вторую он выбирать не может, эта та, которая оказалась за первой, а вдруг в ней бензина совсем нет?

[Smith]

Не, Смит, если бы было так просто, то я бы не мучался и не рисовал график. Я согласен с первой частью Вашего рассуждения, что можно найти эту первую бочку. Хопрошо, он доехал до следующей бочки, а дальше? Первую бочку он выбирал, а вторую он выбирать не может, эта та, которая оказалась за первой, а вдруг в ней бензина совсем нет?

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

[Michael]

Не, Смит, если бы было так просто, то я бы не мучался и не рисовал график. Я согласен с первой частью Вашего рассуждения, что можно найти эту первую бочку. Хопрошо, он доехал до следующей бочки, а дальше? Первую бочку он выбирал, а вторую он выбирать не может, эта та, которая оказалась за первой, а вдруг в ней бензина совсем нет?

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

Возможно, я не так тебя понял, попробуем ещё раз. Почему ты бросаешь своё доказательство так бысто? Первый шаг, и сразу "и так далее". Попробуй сделать второй.
Итак, ты находишь первую бочку, доехал до второй, тут всё чётко. Обьясни мне как ты поедешь до третьей? А вдруг у первой бочки и слева и справа стоят пустые бочки?

[Smith]

Показать скрытый текст

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

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

[Smith]

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

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

[Michael]

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

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

Вроде всё логично, ошибки не вижу. 

[Smith]

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

[Miki]

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

[Smith]

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

Мики, не понял вопроса..
условно говоря, если бы можно было сделать так, чтобы ВСЕ бочки были с излишком, то нам и доказывать ничего не пришлось бы.
еще раз хочу обратить твое внимание на то, что мы пытаемся доказать собственно существование такого пути, а не объяснять, как правильно по нему проехать.
т.е. в жизни существует такой вид доказательства, когда можно просто сесть в машину и проехать по всему пути, но сейчас - не об этом ведь..

[buka]

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

Золотые слова, Мики!
И совсем не обязательно, чтобы бочка с самым большим избытком была та, с которой надо начинать!
---------------
Но я же привёл подробное доказательство без графика и таблиц. Что там непонятно?

[Miki]

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

Мики, не понял вопроса..
условно говоря, если бы можно было сделать так, чтобы ВСЕ бочки были с излишком, то нам и доказывать ничего не пришлось бы.
еще раз хочу обратить твое внимание на то, что мы пытаемся доказать собственно существование такого пути, а не объяснять, как правильно по нему проехать.
т.е. в жизни существует такой вид доказательства, когда можно просто сесть в машину и проехать по всему пути, но сейчас - не об этом ведь..

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

[Smith]

Начнём с некоторой бочки Б0 и запишем для неё:
Бочка 0:
Р00 = 0 (Расход топлива до Б0)
БД0 = 0 (Сколько в баке непосредственно до заправки)
БП0 = Б0 (Сколько в баке после заправки, Б0 - сколько в бочке)
Бочка 1:
Р01 = Р (Расход топлива от Б0 до Б1)
БД1 = БП0-Р01 (Сколько в баке непосредственно до заправки)
БП1 = БД1+Б1 (Сколько в баке после заправки)
Бочка 2:
Р12 = Р - R01 (Расход топлива от Б1 до Б2)
БД2 = БП1-Р12 (Сколько в баке непосредственно до заправки)
БП2 = БД2+Б2 (Сколько в баке после заправки)
И так далее...
В процессе заполнения такой таблицы у нас могут появиться отрицательные числа.
Отрицательное число говорит, что если мы начнём от бочки Б0, то до данной бочки мы доехать не сможем.
Не смущайтесь, ведь мы ещё не едем, мы только заполняем таблицу. Будем дальше её тупо заполнять до тех пор, пока мы не "доберёмся" до начальной точки Б0.
Независимо сколько отрицательных точек было, к бочке Б0 мы подъедем и  в точке Б0 у нас окажется пустой бак - это следует из условия - 100 км, 100л, 1л/км. То, что были отрицательные участки (что говорит о невозможности начать с этой Бочки) - неважно, в балансе для бюрократа будет 0
Теперь мы посмотрим на нашу таблицу, и если в ней есть отрицательные БД, найдём ту бочку, для которой этот отрицательный БД худший, т.е. самый большой по абсолютной величине.
Всё что мы таким образом определили - это с КАКОЙ бочки надо на самом деле  начать в данном направлении (если имеются несколько "наихудших" - то надо начать с любой наихудшей, если нет отрицательных БД, то надо начинать именно с Б0)
Действительно:
Если мы начнём с наихудшей (worst), то вместо дефицита БД_worst, мы получим БД_worst=0.
И во всех остальных местах ситуация улучшится:
БП_worst увеличится на величину этого максимального дефицита и все последующие БД_i увеличатся именно на величину этого дефицита, т.к   
БД_i = БП_i-1 - Р_i-1,i, т.е. они все подымутся на эту величину и отрицательных БД_m не останется.

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

[Miki]

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