Форум умных людей

Автомобиль 2 Логические задачи   Вес: 5 , задача с braingames.ru

Есть кольцевая дорога длиной 100 км, на которой произвольным образом разбросано конечное число бочек с горючим. Суммарное количество горючего в бочках — 100 л, но распределение горючего по бочкам произвольно. Есть автомобиль с расходом топлива 1 л/км и пустым баком вместимостью более 100 л. Можно ли объехать всю дорогу в каком-либо направлении?

Бак пустой изначально. :pinkgirl:
Нужна срочно бочка для заправки с минимумом в 1 л горючего. :help:

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

Меня волнует фраза - "в каком либо направлении"
И как уже сказали, машине нужна канистра для заправки

Так если кольцевая, то либо вперед, либо назад.
Меня больше смущает вот это - просто так такой вес не дают. :yesgirl:

это очень много или мало?!

если можно нужно еще доказать это

Это значит задача сверхсложная. :help:

Это совсем непростая задача. Возможно не совсем понятно условие?
Требуется доказать одно из двух:
А. Либо вцегда можно найти бочку и направление движения, при котором как бы неблагоприятно были бы разбросаны бочки, всегда можно от этой точки начать движение, заправив ПУСТОЙ бак и проехать круг до этой бочки.
В. Либо бочки так можно неудачно разбросать, что с какой бы бочки не начать, весь круг проехать не удастся.
Задача совсем непростая...

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

ps  Идя от обратного можно попытаться создать непроходимый барьер.

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

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

извиняюсь за тафталогию:)

Если хотите, могу дать наводку.
Показать скрытый текст

есть 3 варианта отношений между 2 ближайщими бочками,1-количество бензина точно совпадает с расстоянием, 2-количество недостаточно, 3-есть излишек

пусть каждый напишет свое доказательство на рассмотрение юзерам!

но при наличии 2го, где то появляется 3е, выравнивая вреднее к 1му:)

из условия ясно что движение надо начинать с той бочки где есть излишек

допустим есть n бочек,также допустим в n-1 бочках количество бензина недостаточно,то есть расстояние от 1 до n-1 не покрывается,так как по условию сумма 100 литров=100км, значит в n бочке должно быть такое количество бензина которое компенсирует,то есть можно пройти,но есть и другие случаи,надо и их доказать

Воспользуйтесь моей подсказкой. Она вас приведёт к строгому доказательству.

Buka, вы лучше приведите свое доказательство

Я человек честный   :-[
Я просто знаю эту задачу.
Тем не менее, привожу доказательство под спойлером.
Показать скрытый текст

спасибо, но мне кажется можно и без графиков доказать

Показать скрытый текстУтверждение доказано.

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

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

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

Опять всё наоборот. Бочки могут быть разбросаны как угодно неравномерно. И бензина в них может быть налито абсолютно случайным образом. Единственное, что обеспечивается - это то, что общее кол-во бензина во всех бочках = 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.
(http://freeebayimagehost.com/images/bj2ki9scj155y0i90b1.jpg) (http://freeebayimagehost.com/)
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.

 Michael, я понимаю, что Вы любите индукцию. Но индукция требует особую осторожность - можно попасть в ловушку.
Когда проверяется некоторое свойство для начального n (n = 1 или какой-то другой константе С) и затем, предполагая, что оно справедливо для n=К, доказывается, что оно (это свойство) справедливо для n=К+1, ОЧЕНЬ ВАЖНО, чтобы для начального n присутствовали ВСЕ КОМПОНЕНТЫ этого свойства и никакой компонент не был бы деградирован.
Вы говорите, что для n=1 это очевидно. Да, я согласен. Но для n=1 деградировано такое свойство, как ПРОИЗВОЛЬНЫЙ разлив - он абсолютно детерминирован, поэтому n=1 не годится. Надо начинать как минимум с n=2.
Могу привести пример, поясняющий, почему n=1 в подобныx случаях не канает.

---

Пример.
"Доказывается" по индукции утверждение: "У всех людей без увечий и генетических дефектов глаза одного цвета".
1. Для любой группы людей без увечий и генетических дефектов,   состоящей из n=1 человек глаза одного цвета. Это очевидно.
2. Предполагаем справедливость этого свойства для любой группы таких людей, состоящей из n=К человек.
3. Докажем, что это свойство справедливо для n=К+1.
Возьмём произвольную группу из n=К человек и добавим туда произвольного человека, получив группу из n=К+1 человек. Докажем, что у этого человека должны быть глаза того же цвета, что и у остальных К.
Действительно, если допустить, что у него глаза другого цвета, то исключив из группы другого человека, мы получим группу из n=К человек в которой у одного человека цвет глаз отличается. А это противоречит пункту 2. Следовательно, у этого человека должны быть глаза того же цвета. :)

---

Обратите внимание, механизм Вашего доказательства очень похож на механизм моего "доказательства" - Вы тоже исключаете участок :).
Так что n=1 не годится. Надо n>1 для начала (по крайней мере, для n=2)
Но даже этого недостаточно.
Я Вам могу объяснить, почему дальнейшее доказательство имеет изъян. Но это тонкий момент. Дайте мне знать, что Вам пока ясно моё возражение по поводу n=1.

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

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

К сожалению я не умею рисовать :)
Я постараюсь привести доказательство без графика.
Но мне важна обратная связь, чтобы понять, насколько внятно я объяснил.
Поэтому очень прошу - не стесняйтесь спрашивать. Мне очень важна ваша реакция.
Итак, приступим.

---

Начнём с некоторой бочки Б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 не останется.

---

График, о котором я говорил, просто иллюстрировал бы эти расчёты.
Какие будут вопросы? Задавайте.

...

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

В доказательстве в посте 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.

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

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

(http://freeebayimagehost.com/images/2lyezv3ggzosi4bca75y.jpg) (http://freeebayimagehost.com/)

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

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

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

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

Michael,можете вот эти данные поставить графически?расположенность-бочка 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 - наихудшая. С её и надо начать.

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

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

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

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

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

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

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

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

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

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

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

Мне трудно понять и почувствовать, что Вам не нравится... :(
Хорошо, я постараюсь немного по-другому изложить ход рассуждения.
У нас есть М бочек В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 чтобы точно быть уверенным

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где докакзано? может я пропустил реально..

кстати, строго говоря, бочки с излишком может вообще не быть.. :tianchik:

Смит есть же 100 л бензина  которое покрывает 100 км, а кольцо 100 км

Это доказательство, Смит, это.
Но это СТРОГОЕ доказательство, а не некоторый вариант, который при определённых условиях... и т.д.
1. Всегда можно выбрать некоторую бочку (Б1) и некоторое направление.
2. Если начать с Б1 можно либо проехать круг либо не проехать. Третьего не дано.
3. Если оказывается, что мы не можем проехать ( у нас - дефицит), то, перебирая бочки в том же направлении, мы ВСЕГДА найдём бочку (БХ), начав с которой мы доедем до бочки Б1 в том же направлении.
4. Я показал, что при этом мы подъедем к этой бочке с избытком топлива равным ТОЧНО суммарному дефициту, образовавшемуся от Б1 до БХ и поэтому нам хватит топлива, чтобы проехать теперь от Б1 до БХ.
5. Это значит, что для выбранного произвольно направления  всегда найдётся бочка БХ, начав с которой, мы пройдём весь круг.
6. Выбрав другое (противоположное) направление, мы таким же образом можем найти для него точку БУ, начав с которой, мы сделаем круг в этом направлении. В частном случае (но далеко не обязательно) это может быть та же бочка.

бука, сорри, я же не критиканством занимаюсь, возможно для вас (и для всех) очевидно то, что это доказательство, но если я чего-то не понимаю - я спрашиваю либо сомневаюсь.
1.да
2.да (нельзя быть немножко беременной)
3.вот это не совсем понятно: тоесть, я то знаю, что это так, но у вас это, имхо, не доказано. и потом, если бочка БХ - понятно что такое, то вот, к примеру, Б1 - мне не совсем понятно: это первая следующая по пути к концу пути бочка в любом направлении? или первая, которая удовлетворяет условию, т.е., до которой мы однозначно сможем доехать? и почему, собственно сможем?
4.это я совсем не понял: т.е. мы выехали от БХ в сторону Б1, доехали до нее, заправили в авто бензин из Б1 и теперь нам хватит его чтобы доехать далее по кругу обратно к БХ? а Б2, Б3, Бn?
5.это вытекает из 4? или из 1-4? т.к. 3 и 4 я не понял, то и 5 для меня естественно в непонятках.
6.это на мой взгляд сказано типа "из личного опыта", т.е. мне иногда тоже казалось, что это так. но доказательства пока никто не представил.
вообще, меньше всего хотелось бы разбирать чужие ошибки или собственные непонятки, но без понимания 3-4-5 я, увы, не вижу доказательства в вашем объяснениии.
возможно просто торможу, :tormoz: а возможно .. ???

Смит, Б1 - это случайным образом выбранная нами бочка которую мы выбрали за точку отсчёта. Как только мы её выбрали, все наши рассуждения касаются именно этой бочки Б1.
1. Итак, начав с неё наше виртуальное путешествие, мы либо можем проехать (на бумаге!!!) либо нет. Если можем - ОК, но это не интересно, если не можем, то значит до какой-то бочки (назовём её БП1 - бочка плохая 1) мы доехать не можем.
2. Допустим, мы не можем проехать Х1 км, значит нам на участке Б1-БП1 не хваает Х1 литров бензина. С этим, надеюсь, Вы согласны. Назовём это "Дефицит в Х1 литров"
3. Но это же значит, что на учаске П1-Б1 (направление - то же) у нас есть избыток в Х1 литров. С этим Вы тоже должны согласиться.
4. Начнём движение с БП1 (Бочка Б1 остаётся как точка отсчёта). Начав с БП1 мы либо можем доехать до Б1, либо - нет.
4.1. Если мы можем доехать до Б1, значит мы к ней подъедем с Х1 литрами в запасе (ведь избыток Х1 означает, что на участке БП1-Б1 есть бензина на Х1 км больше, чем длина этого участка). С этим Вы согласны?
4.2. Если мы не можем, то значит что на участке БП1-Б1 есть бочка БП2 до которой мы не доехали (скажем, Х2 км)
Что это значит? Это значит, что на участке Б1-БП1 есть дефицит в Х1 литров, на участке БП1-БП2 - дефицит в Х2 литров, что означает, что на участке Б1-БП2 есть дефицит в Х1+Х2 литров.
4.3. Это же означает, что на участке БП2-Б1 есть избыток в Х1+Х2 литров.
5. Продвигясь виртуально и дальше в этом направлении, мы можем "не доезжать" до БП3 Х3 км, начав с БП3 - до БП4 - Х4 км и т.д.
С каждым таким недоездом наш общий дефицит от Б1 до БПк будет составлять Х1+Х2+...+Хк литров, что автоматически будет означать избыток в Х1+Х2+...+Хк литров на участке БПк-Б1 (Б1 - та же начальная точка Б1, которую мы выбрали)
6. Я утверждаю, что на участке БПк-Б1 ОБЯЗАТЕЛЬНО должна быть бочка БПХ, до которой мы не смогли доехать от предыдущей плохой точки БПм, но с которой мы можем доехать до Б1.
Действительно, допустим обратное: такой бочки не существует. Что это значит?  Значит, если БПХ не нашлась, мы умудрились с какой-то бочки БПп НЕ ДОЕХАТЬ до Б1 таким образом, что между местом нашего НЕДОЕЗДА и Б1 уже нет бочек. (Ведь бочек - конечное число, и если между местом недоезда и Б1 ещё есть бочка (бочки), мы начнём с них. При конечном числе бочек, они должны закончиться когда нибудь и если БПХ не нашлась, то мы оказались в точке Ж, между Ж и Б1 больше нет бочек, но на этом участке (от Ж  до Б1) у нас избыток в Х1+Х2+...+Хк+...+Хм+...+Хп литров!!! (Именно этот избыток образовался, потому что на участке Б1-Ж - дефицит в Х1+Х2+...+Хк+...+Хм+...+Хп литров.
Что же получается? Мы в точке Ж, не можем доехать до Б1 Хж километров, т.е. ещё дефицит в Хж литров и при этом у нас одновременно в этой точке избыток в Х1+Х2+...+Хк+...+Хм+...+Хп литров. Нонсенс.
Этот нонсенс возник из предположения, что БПХ не существует.
7. Итак, мы доказали, что БПХ существует. Значит мы можем доехать до Б1, причем к моменту подъезда к Б1 у нас будет тот суммарный избыток бензина который и РАВЕН В ТОЧНОСТИ тому дефициту, который мы насчитали, виртуально мытарствуя от Б1 через все наши бочки...
Поэтому, начав с БПХ мы сможем НЕ ТОЛЬКО доехать до Б1, но с неё - до БПХ.
-------------------
Что Вам непонятно, Смит?

Что Вам непонятно, Смит?


а его лучше утопить :)

сорри, до завтра!  :bye:
зы: (продолжение следует) :peace:

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

бука. читайте лс..

Я не совсем понял, что Вас смущает.
Моё д-во базируется на следующих моментах:
1. Общее кол-во топлива в бочках = длине круга * на расход.
2. Бочек - КОНЕЧНОЕ число.
------------------------------------------------------------
Мне ВАЖНО знать, что не хватает в д-ве, что Вас смущает...

бука! идите в.. Показать скрытый текст!!