Страниц: 1 ... 4 5 [6]
  Печать  
Автор Тема: Авто 2  (Прочитано 26271 раз)
0 Пользователей и 1 Гость смотрят эту тему.

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

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

Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #75 : Май 09, 2010, 12:02:23 �

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

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #76 : Май 09, 2010, 12:09:29 �

кстати, строго говоря, бочки с излишком может вообще не быть.. Tianchik
Записан
Miki
Гений
*****
Offline Offline

Сообщений: 827

СПАСИБО
-вы поблагодарили: 21
-вас поблагодарили: 49



Просмотр профиля
Ответ #77 : Май 09, 2010, 12:19:36 �

кстати, строго говоря, бочки с излишком может вообще не быть.. Tianchik
Смит есть же 100 л бензина  которое покрывает 100 км, а кольцо 100 км
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #78 : Май 09, 2010, 12:22:34 �

Начнём с некоторой бочки Б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 Smiley
Теперь мы посмотрим на нашу таблицу, и если в ней есть отрицательные БД, найдём ту бочку, для которой этот отрицательный БД худший, т.е. самый большой по абсолютной величине.
Всё что мы таким образом определили - это с КАКОЙ бочки надо на самом деле  начать в данном направлении (если имеются несколько "наихудших" - то надо начать с любой наихудшей, если нет отрицательных БД, то надо начинать именно с Б0)
Действительно:
Если мы начнём с наихудшей (worst), то вместо дефицита БДworst, мы получим БДworst=0.
И во всех остальных местах ситуация улучшится:
БПworst увеличится на величину этого максимального дефицита и все последующие БДi увеличатся именно на величину этого дефицита, т.к   
БДi = БПi-1 - Рi-1,i, т.е. они все подымутся на эту величину и отрицательных БДm не останется.
бука - это? может рассматриваться как вариант, но как по мне Вы скорее доказваете, что предложенный Вами вариант при определенных условиях может оказаться рабочим. а затем пытаетесь проиллюстрировать собственно систему движения.
вопрос же звучит так: можно ли проехать вообще? иными словами - существует ли такой путь всегда - не зависимо от тго, как размещены бочки и сколько их всего.
я просто пытаюсь составить лаконичное и убедительное доказательство и предлагаю всем поучавствовать.
Это доказательство, Смит, это.
Но это СТРОГОЕ доказательство, а не некоторый вариант, который при определённых условиях... и т.д.
1. Всегда можно выбрать некоторую бочку (Б1) и некоторое направление.
2. Если начать с Б1 можно либо проехать круг либо не проехать. Третьего не дано.
3. Если оказывается, что мы не можем проехать ( у нас - дефицит), то, перебирая бочки в том же направлении, мы ВСЕГДА найдём бочку (БХ), начав с которой мы доедем до бочки Б1 в том же направлении.
4. Я показал, что при этом мы подъедем к этой бочке с избытком топлива равным ТОЧНО суммарному дефициту, образовавшемуся от Б1 до БХ и поэтому нам хватит топлива, чтобы проехать теперь от Б1 до БХ.
5. Это значит, что для выбранного произвольно направления  всегда найдётся бочка БХ, начав с которой, мы пройдём весь круг.
6. Выбрав другое (противоположное) направление, мы таким же образом можем найти для него точку БУ, начав с которой, мы сделаем круг в этом направлении. В частном случае (но далеко не обязательно) это может быть та же бочка.
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #79 : Май 09, 2010, 17:32:15 �

Это доказательство, Смит, это.
Но это СТРОГОЕ доказательство, а не некоторый вариант, который при определённых условиях... и т.д.
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 я, увы, не вижу доказательства в вашем объяснениии.
возможно просто торможу, Тормоз а возможно .. Huh?
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #80 : Май 09, 2010, 21:52:06 �

Это доказательство, Смит, это.
Но это СТРОГОЕ доказательство, а не некоторый вариант, который при определённых условиях... и т.д.
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 я, увы, не вижу доказательства в вашем объяснениии.
возможно просто торможу, Тормоз а возможно .. Huh?
Смит, Б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, но с неё - до БПХ.
-------------------
Что Вам непонятно, Смит?

Эти пользователи сказали вам СПАСИБО :

Redirect

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Май 10, 2010, 01:39:27 от buka Записан
sek140675
Гений-Говорун
*
Offline Offline

Сообщений: 1861

СПАСИБО
-вы поблагодарили: 283
-вас поблагодарили: 108



Просмотр профиля Email
Ответ #81 : Май 09, 2010, 21:55:45 �

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


а его лучше утопить Smiley
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #82 : Май 09, 2010, 22:03:30 �

сорри, до завтра!  Пока
зы: (продолжение следует) Мир
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #83 : Май 10, 2010, 09:04:23 �

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

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #84 : Май 10, 2010, 15:05:57 �

бука. читайте лс..
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #85 : Май 10, 2010, 15:39:00 �

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

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #86 : Май 10, 2010, 15:40:51 �

бука! идите в.. Показать скрытый текст!!
Записан
Страниц: 1 ... 4 5 [6]
  Печать  
 
Перейти в: