Название: Кэмэл трофи, типа..)
Отправлено: Smith от Октябрь 31, 2012, 12:59:31
Вы на своем грузовике хотите путешествовать по пустыне. Вы знаете, что всё, что Вам необходимо для путешествия на один день (топливо, продукты питания и т.д.) может быть собрано в один "большой ящик", но Ваш грузовик может перевозить максимум 10 больших ящиков. В пустыне невозможна никакая дозаправка ни чем, но в начале путешествия поставка "больших ящиков" не ограничена.
Предложите план Вашего путешествия и сообщите, сколько дней это, на Ваш взгляд, займет, если:
1. Вы знаете, что расстояние, которое Вам необходимо преодолеть составляет 12 дней путешествия по пустыне.
2. ... 20 дней ...
3. ... 100 дней ...
4. Какова должна быть Ваша стратегия, если Вам предстоит преодолеть всю пустыню, но Вы не знаете её размеров?
Название: Re: Кэмэл трофи, типа..)
Отправлено: fortpost от Октябрь 31, 2012, 13:29:15
Показать скрытый текст
1. Берем 10 ящиков, едем 2 дня, 6 ящиков выгружаем, 2 дня возвращаемся. Берем 6 ящиков, едем 2 дня, забираем оставленные 6, едем 10 дней. Итого 2+2+2+10=16 дней.
Название: Re: Кэмэл трофи, типа..)
Отправлено: Smith от Октябрь 31, 2012, 16:04:10
та да :yesgirl:
Название: Re: Кэмэл трофи, типа..)
Отправлено: Smith от Ноябрь 01, 2012, 17:16:34
меня 4-й пункт сильно напрягает :o
Название: Re: Кэмэл трофи, типа..)
Отправлено: fortpost от Ноябрь 01, 2012, 23:02:47
У М. Гарднера есть аналогичная задача, но там разрешается дробить запас на как угодно мелкие части. Показать скрытый текст
Приводимое ниже решение задачи о том, как пересечь пустыню, заимствовано из журнала Eureka, издаваемого студентами-математиками университета в Кеймбридже (Массачусетс). Назовем «единицей» расстояние в 500 миль, одной заправкой — количество бензина, необходимое для того, чтобы проехать 500 миль, и рейсом — поездку, совершаемую грузовиком в любом направлении от одной остановки до другой.
Две заправки позволяют грузовику пройти максимальное расстояние в 4/3 единицы. Для этого необходимо совершить четыре рейса. Сначала на расстоянии 1/3 единицы от пункта отправления строится бензохранилище: грузовик полностью заправляют (на это уходит 1 заправка), после чего он едет к бензохранилищу, оставляет там 1/3 заправки и возвращается назад. Его снова полностью заправляют (на что уходит еще 1 заправка). Он опять едет к бензохранилищу и забирает оставленную там 1/3 заправки (таким образом, он снова оказывается полностью заправленным). После этого он может проехать еще расстояние в 1 единицу.
Три заправки позволят грузовику проехать расстояние в 4/3 + 1/5 единицы, причем для этого потребуется совершить девять рейсов.
Сначала на расстоянии 1/5 единицы от пункта отправления строят бензохранилище и завозят в него 6/5 заправки. На это уходят три рейса. Затем грузовик возвращается, полностью заправляется (на что уходит последняя заправка) и прибывает к первому хранилищу, имея в своих баках 4/5 заправки. Вместе с уже имеющимся в бензохранилище топливом это количество составляет две полные заправки, что достаточно для того, чтобы грузовик мог пройти еще 4/3 единицы расстояния (как это сделать, мы только что объяснили).
Нам осталось еще ответить на второй вопрос о минимальном количестве бензина, необходимом для того, чтобы грузовик мог проехать 800 миль. Три заправки, как мы только что выяснили, позволяют грузовику покрыть расстояние в 766∙2/3 мили (4/3 +1/5 единицы), поэтому на расстоянии 33∙1/3 мили (1/15 единицы) от пункта отправления необходимо построить еще одно (третье) бензохранилище. За пять рейсов экипаж грузовика сможет построить это хранилище и завезти в него столько горючего, что, когда в конце седьмого рейса грузовик поравняется с третьим хранилищем, общее количество бензина в его баках и в хранилище составит три заправки.
Как мы уже знаем, этого количества топлива достаточно для того, чтобы грузовик смог пройти оставшееся расстояние в 766∙2/3 мили. На семь рейсов, совершенных между пунктом отправления и вновь построенным бензохранилищем, израсходовано 7/15 заправки.
Трех оставшихся заправок как раз достаточно для того, чтобы проехать оставшуюся часть пути. Таким образом, на весь путь будет израсходовано 3∙7/15, или больше 3,46, заправки. Всего потребуется совершить шестнадцать рейсов.
Рассуждая в том же духе, можно показать, что, имея четыре заправки, грузовик сумеет проехать расстояние в 1∙1/3 +1/5 + 1/7 единицы.
На границах отрезков пути длиной в 1∙1/3, 1/5 и 1/7 следует расположить бензохранилища. С увеличение числа заправок этот бесконечный ряд расходится, поэтому грузовик сможет пересечь пустыню любой ширины. Если ширина пустыни 1000 миль, то для преодоления этого расстояния потребуется построить 7 бензохранилищ, совершить 64 рейса и израсходовать 7,673 заправки бензина.
В связи с этой задачей редакция получила сотни писем с общими решениями и интересными замечаниями. Сесил Дж. Филлинс, профессор математики Флоридского университета, следующим образом сформулировала существо дела.
Общее решение задачи дается формулой
d=m(1+1/3+1/5+1/7+...)
где d — ширина пустыни, которую необходимо пересечь, m — число миль, отнесенных к одной заправке бензина. Число бензохранилищ, которое необходимо построить, на единицу меньше числа членов в отрезке ряда, который следует взять для получения данного d. На поездки между любыми двумя станциями расходуется одна заправка. Поскольку ряд расходится, метод позволяет преодолеть пустыню любой ширины, хотя необходимое количество бензина с увеличением расстояния возрастает экспоненциально.
Если грузовик в конце путешествия возвращается в исходный пункт, то формула имеет вид
d=m(1/2+1/4+1/6+...)
Этот ряд также расходится, и свойства решения аналогичны свойствам решения для случая, когда грузовик обратно не возвращается.
|