Авто 2

[Miki]

Buka, не могли вы бы показать свой график,если возможно?

[badscaremonger]

ну а ели бочки всего две.Первая в начали пути с 1л. а вторая ровно на середине с 99л. то как тогда проехать.
Мой ответ не всегда

[buka]

Buka, не могли вы бы показать свой график,если возможно?

К сожалению я не умею рисовать
Я постараюсь привести доказательство без графика.
Но мне важна обратная связь, чтобы понять, насколько внятно я объяснил.
Поэтому очень прошу - не стесняйтесь спрашивать. Мне очень важна ваша реакция.
Итак, приступим.Начнём с некоторой бочки Б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 не останется.График, о котором я говорил, просто иллюстрировал бы эти расчёты.
Какие будут вопросы? Задавайте.

[Michael]

...

[Smith]

ну а ели бочки всего две.Первая в начали пути с 1л. а вторая ровно на середине с 99л. то как тогда проехать.
Мой ответ не всегда

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

[Michael]

В доказательстве в посте 28  всё правильно, но один момент хотелось бы уточнить. Принцип такой - любой маршрут при N=6 (доказанный случай) превращается в искомый маршрут при N=7 путём возвращения бочки 4 на своё законное место. Например маршрут 2-3-5-6-7-1-2 (для N=6) превращается  в маршрут 2-3-4-5-6-7-1-2 (для N=7).   Кроме одного случая!   В случае, когда маршрут для 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 , и дальше всё идёт как по маслу! Я добавил это изменение в пост 28 в виде пункта 8.

[Miki]

Buka, вот например: расположенность-бочка 8л-расстояние 5км, 3л-10км, 16л-11км, 4л-6км, 7л-3км, 12л-14км, 5л-2км, 14л-15км, 22л-11км, 9л-23, как вы тут найдете ? в этой задаче мне кажется нужно логически доказать что в любом случае есть такая бочка и почему она должна быть

[Michael]

Сразу после доказательства в посте 28, я придумал прямое доказательство утверждения задачи, но не знал как сделать чертёж, чтобы он выглядел не очень отпугивающе (я обьясню в чём была сложность). Сейчас попробую привести доказательство, надеюсь будет понятно (если кому-то это ваще интересно).
Допустим маршрут движения такой - 1-2-3-4-5-6-7-8-9-10-11-1. На графике на оси абсцисс (Х) откладываем пройдённое расстояние, на оси ординат (Y) откладываем количество бензина в автомобиле. При этом, если бензин кончился, мы продолжаем двигаться, количество бензина становится отрицательным, не надо этого бояться, просто представьте что рядом с нами едет заправщик и в случае необходимости мы одалживаем бензин у него. Отрицательное количество бензина в баке означает что мы задолжали бензин (отрицательный баланс), потом отдадим. Задача состоит как раз в том чтобы проехать по всему маршруту и ни разу не одолжить бензин.   
Итак, в начальной точке (пункт 1), бензин=0 (отмечаем это на осиY) Затем заправляемся бензином из бочки 1 и едем до пункта 2, текущее количество безина (до заправки из бочки 2)отмечаем на оси Y (оно может быть и отрицательным), и т.д. пока не доберёмся в пункт 1. Получился следующий график.

//текст доступен после регистрации//

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

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

Новый график получается так: правую часть старого графика (от 6 до 1) переносим в начало, левую часть(от 1 до 6) переносим в конец.

Ниже уровня пункта 6 мы никогда не сможем опуститься (мы его так выбирали). Но мы начинаем маршрут с него, а в начальной точке уровень бензина всегда равен 0. Значит, мы никогда не опустимся ниже 0, то есть нам не придётся одалживать бензин, и мы проделаем весь маршрут на своём.

[Miki]

Michael,можете вот эти данные поставить графически?расположенность-бочка 8л-расстояние 5км, 3л-10км, 16л-11км, 4л-6км, 7л-3км, 12л-14км, 5л-2км, 14л-15км, 22л-11км, 9л-23

[Michael]

Мики, сделаю чуть-чуть позже , ОК? Что-то с графиками сегодня не ладится.

[buka]

Buka, вот например: расположенность-бочка 8л-расстояние 5км, 3л-10км, 16л-11км, 4л-6км, 7л-3км, 12л-14км, 5л-2км, 14л-15км, 22л-11км, 9л-23, как вы тут найдете ? в этой задаче мне кажется нужно логически доказать что в любом случае есть такая бочка и почему она должна быть

Хорошо, будем составлять таблицу.
Первая колонка - Номер Бочки (НБ)
2-я - Сколько в ней бензина  (Б)
3-я - Расстояние до следующей (= расходу до следующей) (РС)
4-я - Сколько бензина в Баке Машины до заправки (БД)
5-я - Сколько бензина в Баке после заправки (БП)
НБ  Б РС   Бак--До    Бак-После
 1  8  5         0            8
 2  3 10     8-5=3    3 + 3 = 6
 3 16 11   6-10=-4   -4 +16 =12
 4  4  6  12-11= 1    1 + 4 = 5
 5  7  3   5-6 =-1   -1 + 7 = 6
 6 12 14   6-3 = 3    3 +12 =15
 7  5  2  15-14= 1    1 + 5 = 6
 8 14 15   6- 2= 4    4 +14 =18
 9 22 11  18-15= 3    3 +22 =25
10  9 23  25-11=14   14 + 9 =23
 1  0  0  23-23= 0            0
Обратите внимание на бочки 3 и 5. Они имеют в колонке Бак--До отрицательные числа. Это значит, что они "плохие" для бочки 1 (если с неё начать).
Причём Бочка 3 - наихудшая. С её и надо начать.

[Miki]

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

[Michael]

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

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

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

[Michael]

Извините, я спутал 2 разных доказательства, моя цитата относилась к доказательству по индукции, а ваш вопрос - к прямому доказательству. Запутался.
=======
Как я сказал выше, на графике должна быть самая нижняя точка, правильно? С неё и надо начинать.