Верблюд в пустыне -- задача

Lokomotiv59

Верблюд в пустыне
Верблюд должен пройти через пустыню к ближайшему городу, который располагается на расстоянии 1000 км. В начале пути он располагает 3000 литрами воды, однако может на себе нести не более 1000 литров воды. За каждый километр пройденного пути он выпивает один литр воды. Верблюд может оставлять воду в пустыне и потом забирать ее. Какое максимальное количество воды он может перенести в город?
Нашел эту задачу на одном форуме в разделе "Детские задачи". В общем интуитивно понимаю, что правильный ответ — 1600/3, и даже могу построить соответствующий пример. Задача в том, чтобы строго доказать, что это значение — действительно максимальное.

Damrad

Нашел эту задачу на одном форуме

а теперь найди на другом форуме правильный ответ с полным решением

Lokomotiv59

Уже пробовал — либо доказательство вообще не приводят, либо в качестве доказательства пишут какой-то бред :crazy:
А вообще просьба высказываться ближе к теме.

Sensor4ik

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

Lokomotiv59

Еще раз: нужно строгое доказательство. По приведенной ссылке я его не нашел. Верблюд может как угодно "размазывать" воду по пустыне, а потом ее забирать, а также произвольное число раз менять направления движения. Я не уверен, что такие рассуждения могут быть доведены до строгого доказательства:
Про первые 200 м - в принципе не важно по скольку их идти, можно хоть по 1 м туда-сюда бегать с полной нагрузкой (в смысле туда- с нагрузкой, обратно - с одним бананом на дорогу все равно сожрет ровно 1000 бананов. Хитрость в том что вот если идти сразу более чем на 200 м - это будет уже в минус, ибо 1000 бананов съедается на 200-х метрах и получаются уже ровно 2 загрузки слонов (2000 бананов и теперь бегать надо не туда-обратно, туда-обратно, туда, а просто туда-обратно, туда. То есть если мы сразу пройдем больше 200 метров, то слон в итоге три заза пройдет участок свыше отметки 200 м, который мог бы проити всего 2 раза - а больше путь=> больше сожрет То же и с последующими 333 метрами (оставляем ровно на одну загрузку)
Вот еще один пример "доказательства" (из Интернета):
Очевидно, что принести в город больше 1000 л. верблюд не сможет в принципе. Очевидно также, что путь придется делить на n этапов. Следовательно, оставлять больше 1000 литров перед последним n-ным этапом попросту нет смысла - все что сверх 1000 придется там и оставить, ибо возвращаться за ней будет накладно; А оставлять меньше 1000 - невыгодно, т.к. верблюд получается недоиспользован. Следовательно, к началу n-ного этапа там должно находиться ровно 1000 литров воды. Рассуждая аналогичным образом для всех n-1, n-2 и т.д. этапов, получаем, что а) этапов должно быть всего три, т.к. воды изначально 3000 литров, при этом на каждом этапе должно тратиться ровно 1000 литров, кроме последнего этапа; б) протяженность каждого этапа должна быть различной, причем протяженность первых этапов - меньше, т.к. по ним придется сделать больше рейсов.
На самом первом этапе верблюду придется возвращаться за водой дважды, следовательно всего он сделает 5 рейсов на этом этапе (туда-обратно дважды и еще один раз туда). Следовательно, протяженность первого этапа должна составить 1000/5 = 200 км. На втором этапе исходное количество воды не будет превышать 2000 литров, следовательно за водой придется возвращаться лишь один раз, сделав 3 рейса (туда-обратно и снова туда следовательно, протяженность второго этапа должна составлять 1000/3=333 км, т.к. к началу третьего этапа больше 1000 литров оставлять бесполезно. Протяженность третьего этапа чисто арифметически составляет 467 км. Таким образом, максимальное число воды - 533 литра.

toxin

Пока придумал лишь следующие упрощения, которые позволяют уменьшить пространство стратегий верблюда: дадим ему новую сверхспособность - он может в любой момент телепортировать воду в точку более далекую от города. В таком случае приближение воды к городу увеличивает ее ценность в любой ситуации. В таком случае не имеет смысл оставлять воду не меняя направление движения, двигаться от города неся воду (мы непрерывно телепортируем воду от источника ближе нас к городу и выпиваем) и брать из источника не min(1000,размер источника) литров. Еще можно заметить, что если мы где-то оставили воду, то нельзя забирать ее приходя от города - иначе можно было оставить ее чуть дальше и потом взять чуть ближе от города.

kshangin

То есть верблюд изначально знает, в какой стороне город? Я было сначала подумал, что это усложненная вариация другой задачи, когда надо выйти из леса, зная, что край на каком-то расстоянии, но не зная направления...
/а забавное усложнение, кстати...

svetik5623190

Пока придумал лишь следующие упрощения, которые позволяют уменьшить пространство стратегий верблюда: дадим ему новую сверхспособность - он может в любой момент телепортировать воду в точку более далекую от города. В таком случае приближение воды к городу увеличивает ее ценность в любой ситуации.
Понятия из теории игр, условие free disposal of utility... :) Вы в РЭШ не учились ли, коллега? ;)

plot

не писал бы в форуме, давно бы решил. тем более не такая уж сложная задача, чтобы решение спрашивать. Гораздо приятнее его самому найти =)

Lokomotiv59

Если бы я сам смог решить эту задачу, я бы сюда не писал. Но пока, к сожалению, сабж решить не удалось. Был бы признателен тебе, за помощь в решении этой несложной задачи. :smirk: А если тебе все же нечего написать по существу, то лучше тебе было вообще ничего не писать.

Lokomotiv59

Да, это ценное замечание, спасибо за идею :)

toxin

Вы в РЭШ не учились ли, коллега?
Нет, я с мехмата. Просто теория игр (как и многое другое в математике) меня интересует с детства.

gr_nik

Мне кажется, можно как-то так:
Введём ограничение на передвижения верблюда (пока не уверен, насколько велика потеря строгости от этого). Ограничение следующее: он может разворачиваться не более чем конечное количество раз. В таком случае множество точек разворота верблюда образуют некоторое разбиение отрезка [0;1000]. Теперь рассмотрим следующую задачу: пусть на пути [0;1000] дано конечное количество точек (назовём их «стоянками» и верблюд может двигаться как угодно, но разворачиваться и оставлять воду ему разрешается только на стоянках. Тогда если мы посмотрим на один такой конкретный отрезок между двумя стоянками, то если его рассматривать независимо от остальных участков, то в начальной стоянке этого отрезка за всё время побывало некоторое количество воды, и в конце некоторое количество воды оказалось в конечной стоянке этого отрезка (когда мы смотрим на этот отрезочек, нам не важно, везли ли воду куда-то из этой точки или нет). Здесь я замечу, что между проходами по этому отрезку, могли находиться произвольные передвижения по другим кускам пути, но нам они не важны, мы смотрим только сколько воды в итоге за всё время было принесено в начальную и конечную точки отрезка. Тогда понятно, что если вначале воды было не более, чем 1000 литров, то быстрее всего её перегнать за один раз, если не более 2000 литров, то за 2 раза, если не более 3000 литров, то за 3 раза. В первом случае на прохождение отрезка длиной t тратится не менее t литров, во втором – не менее 3t литров, а в третьем – не менее 5t литров.
Теперь заметим, что чем ближе находится точка, до которой доехало 2000 литров воды, к конечному пункту, тем лучше (иначе можно было бы просто вылить часть воды в более ранней точке). Поскольку до этой точки все отрезки третьего типа, то придётся затрачивать не менее 5t литров на километр пути. Значит, отметка 2000 находится не дальше чем (3000-2000)/5=200 от начала пути. Аналогично, отметка 1000 находится не дальше чем (2000-1000)/3=333&1/3 от отметки 2000. Ну и дальше транспортировка отнимает не менее чем длина оставшегося пути, то есть (1000-200-333&1/3).
Итого у нас остаётся 533&1/3 литров воды.
Как это, более-менее строго?

blackout

Похоже на правду.

Manbox

Эээм, а зачем ограничение? Просто верблюд перетаскивает всю воду на 1 км вперед (и получается совсем школьное решение без множеств, разбиений и пр. да и хоть на dx, ничего же в результате не меняется, на повороты он воду не тратит =)
Почему этот алгоритм правильный. Пусть z это количество донесенной воды, e = z/3000 - некая эффективность. Разобьем участок на три части, двумя точками на которых осталось 1000 и 2000 л воды. Получим отрезки длиной 1000-x-y,y,x, с расходом воды на продвижение вперед на 1 со-но 1,h1,h2. Запишем уравнения связывающие эти величины:
z = 3000 - (1000- (x+y - y*h1 - x*h2
y*h1=1000
x*h2=1000
откуда эффективноть
e = 1/3 (h1 + h2)/h1*h2
по построению h1 >= 3, h2>=5, со-но при их минимальных значениях мы и получаем максимальное значение, если же мы разобьем изначальный путь всего на два отрезка или не разобьем, то простой арифметикой можно убедится что эфф будет только меньше.
вот

gr_nik

Ну в моём решении тоже всё это есть, только буквами h1, h2, x, y и z не обозначено. Просто то, что ты пишешь, не формализовано никак. Откуда эта "эффективность" берётся? Почему именно так?

Lokomotiv59

К этому решению есть два вопроса:
1) Если в начале отрезка было 1001 литр (не более 2000 литров а t равно, к примеру, 100 км, то оптимально будет перегнать 900 литров за 1 ходку, а не 701 литр за 2.
2) (главный вопрос) Почему оптимальное прохождение всей трассы достигается оптимальным прохождением каждого из участков? Другими словами, как оптимальное прохождение маленького участка связано с оптимальной стратегией верблюда?
Пока я дошел до того, что можно считать, что для оптимальной стратегии (достигается модификациями стратегии, не ухудшающими результат):
1) верблюд оставляет воду только в конечном числе точек, и меняет направление движения только в этих точках;
2) в конце движения воды в пустыне не осталось, за исключением, быть может, начальной точки;
3) при повороте "от города - к городу" верблюд берет максимально возможное количество воды;
4) при повороте "к городу - от города" верблюд сбрасывает всю воду
5) при движении к городу верблюд воду не оставляет
6) при движении от города верблюд идет порожняком, пьет воду "телепортируя" ее из более близких к городу источников

Manbox

Просто то, что ты пишешь, не формализовано никак. Откуда эта "эффективность" берётся? Почему именно так?
 :grin: А с каких пор отношение того что стало к тому что было, при том что изначально всегда было 3000 л., непонятно откуда берется? Самый замечательный параметр, что бы не рисовать всякие тысячи и прийти к одной системе оценки прохождения, а не мерятся литрами =)
Если мое решения не формализовано, то что ж ты не написал 3 уравнения из которых видно как получается что это решение верное, плюс еще и сделал свое в рамках непонятно зачем взявшегося предположения? =)
Вообще ответы у всех одинаковые и правильные, так что предлагаю обсуждать почему такой алгоритм перетаскивания тут единственно верен, а не обсуждать недостатки решений =)

blackout

2) (главный вопрос) Почему оптимальное прохождение всей трассы достигается оптимальным прохождением каждого из участков? Другими словами, как оптимальное прохождение маленького участка связано с оптимальной стратегией верблюда?
Как согласившийся с решением попробую его объяснить:
Мы на каждом отрезке ставим счетчик воды, которая проходит к городу (каждый литр считается один раз). Если через счетчик прошло больше, чем 1000л, то за одну ходку ее не пронести, значит через этот счетчик верблюд прошел минимум 3 раза. А значит и через весь отрезок он прошел минимум 3 раза.
Также заметим, что показания счетчиков монотонно убывают при приближении к городу. То есть сначала идут отрезки , пройденные минимум 5 раз, потом минимум 3, потом минимум 1.

Manbox

) тут все решения строятся для данного условия школьной задачи а не общего случая. Если же рассуждать без конкретных цифр, то единый алгоритм получается довольно сложным, в нем в любом случае должна присутствовать некая логика, выбирающая, в зависимости от расстояния, кол-ва воды и вместимости верблюда, дельнейшие действия. Прогу, решающую эту задачу, сделать еще ладно, а вот единой формулой ответ написать...
2) что значит оптимальное прохождение трассы и участков? Если составить функцию, содержащую некий алгоритм действий, количества воды которое верблюд донесет до города, то это и будет связь. В частном случае, как в задаче, оптимальное прохождение участков приводит к оптимальному прохождению всей трассы. В общем - нет.
1) А если кол-во точек будет бесконечно это изменит результат?

Lokomotiv59

Да, спасибо. Теперь все стало ясно :D

iri3955

Пусть верблюд всё отходил.
Тогда через отметку x, от прошёл вперёд n + 1 раз, назад n раз (если он остановился в x и пошёл назад, то счтаем, что он не проходил отметку x)
Тогда, он может с тем же результатом сначала отходить свой путь от 0 до x (с тем же кол-вом воды оставляя недонесённую воду в x, а затем пройти оставшийся путь от x до 1000. Воды ему очевидно хватит как на обратный путь от x до 0, так и на оставшийся путь от x до 1000.
Поэтому ля любой точки x мы можем сказать, что он сначала нёс воду до неё, а затем дальше.
Дальше берём x = 200. Очевидно, что на этой отметке, когда он будет идти дальше у него будет не более 2000 литров (если больше, то через каждую точку от 0 до 200 он прошёл не менее 5 раз (пронёс через неё более 2000 литров, а значит не менее чем за 3 захода + 2 обратно а на это ему не хватит воды).
аналогично, при x = 200 + 1000 / 3 остаётся не более 1000 литров.
А дальше до отметки 1000, он идёт одной ходкой.

Sergey79

Задача в том, чтобы строго доказать, что это значение — действительно максимальное.
вроде уже нашли ответ. Но вот еще такие рассуждения:
0) Вместимость верблюда V, Объем воды n*V
1) Так как верблюд может совершать сколько угодно точек поворота, то считаем, что вся вода по пустыне движется непрерывно, но скачкообразно меняется ее расход:
на каждом отрезке x_i расход воды (2i-1)*x_i
2) Длина отрезка x_i=V/(2i-1) - так как переход x_i потребит V воды.
3) Выбег верблюда по пустыне до полного израсходования воды
[math]$X=\sum_{i=1}^{n}x_i=V\sum_{i=1}^{n}\frac{1}{2i-1}$[/math].
4) Текущее количество воды в точке x есть v(x).
5) Далее необходимо определить на какой участок x_m попала координата x
[math]$x=V\sum_{i=m+1}^{n}\frac{1}{2i-1}+y$[/math], где y<x_m.
6) Тогда
[math]$v(x)=nV-V(n-m)-y(2m-1)=V(m-y/V(2m-1$[/math],
поскольку на каждом из n,..,m+1 отрезков расход воды ровно V, и есть еще неполный расход участка m.
7) В наших условиях n=3, x=V. Тогда x_3=V/5, x_2=V/3, x_1=V. Отсюда m=1 - город на участке x_1, y/V=1-1/3-1/5=7/15. В итоге: v(V)=V(1-7/15)=8000/15=1600/3.

Sergey79

еще конечно можно уйти от соответствия литр=километр в этой задаче, но это просто дополнительные множители в формулах.
Оставить комментарий
Имя или ник:
Комментарий: