Исследование операций (хомячных)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 02 апр 2020, 09:59

Чтобы выжить зимой, жадный голодный хомяк решил ограбить ореховый заводик, находящийся в 1000 м от его норы. На заводике осталось 3000 орехов. В щеки хомяка помещается максимум 1000 орехов. Куда и с чем бы ни шел хомяк, каждый метр ему необходимо подкрепляться 1 орехом. Хомяк уже на заводике и опасен. Какое максимальное число орехов он сможет запасти?

Надо не забыть, что холостой метр тоже требует ореха

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Исследование операций (хомячных)

Сообщение zykov » 02 апр 2020, 10:36

Ему надо набрать 1000 орехов, отнести их на какое-то расстояние $d_1$ (менее 500м), там часть выложить, оставив у себя ровно столько, чтобы вернутся на завод. И так ещё 2 раза, пока на заводе не кончатся орехи. Этот участок он пройдёт 5 раз. Значит истратит $5d_1$ орехов.
Потом так же переносить от этой точки до другой. Если на первой точке было более 2000 орехов, то 5 раз нужно пройти. Если от 1001 до 2000, то 3 раза. Если не более 1000, то уже можно 1 раз пройти.

Понятно, что желательно, чтобы суммарное расстояние, где тратится по 5 проходов, было минимизировано.
Т.е. первая $d_1$ должна быть 200м. Он истратит 1000 орехов и ему нужно будет перенести 2000 орехов на расстояние 800м.
Далее, $d_2$ должно быть 333м. Он истратит 999 орехов и ему нужно будет перенести 1001 орех на расстояние 467м.
Оставшееся расстояние он проходит один раз. Один орех придется выбросить, т.к. влезает только 1000.
Истратит он 467. Запасено будет 1000-467=533 ореха.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 02 апр 2020, 11:30

А например доказательство что нельзя запасти больше?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Исследование операций (хомячных)

Сообщение zykov » 02 апр 2020, 11:40

Там вроде как очевидно.
Если $d_1$ меньше 200м, то либо ещё ходить 5 раз - тут всё равно важно суммарное расстояние, либо начинать ходить по 3 раза (заберем всё равно максимум 2000 орехов, остальное выбросим), но тогда расстояние будет больше 800м - значит расход будет больше.
Если $d_1$ больше 200м, то на каждый лишний метр тратим по 5 орехов - убыток.
Аналогично с $d_2$, где ходим по 3 раза.
Если $d_2$ будет 334м вместо 333м, то сэкономим мы 2 ореха - выбрасывать один не надо и 1м для последнего прохода. Но теряем 3 ореха - 1м и 3 прохода.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 02 апр 2020, 12:06

Вот сравните. действий у хомяка помногу в каждый момент.
Выбираем тот прием, который указан здесь https://math.ru/lib/460 но не указан (а зря) здесь https://ru.wikipedia.org/wiki/Олимпиадн ... кие_задачи
-сокращаем возможные стратегии хомяка до тех, которые гарантированно содержат искомый оптимум (точнее, выброшенные не содержат строгого оптимума), но "системны". А именно, пусть хомяк еще боится что орехи украдет другой хомяк, и держит весь запас орехов не далее метра от себя, то есть -метр вперед с орехами- метр назад пустой и все, никаких иных действий не делает. Из любых его разумных действий -простой перестановкой во времени можно получить такие, и значит ответ не изменится от этого уточнения.
Обозначим расстояние до дома хомяка за n, а [math]- наибольшее количество орехов, которые он мог бы сюда доставить. [math]
Обсуждается формула
[math]-казалось бы справедливая, хомяк когда орехов на N=3,2,1 ходок, должен сходить 2N-1 раз в пределах между n-м и (n+1)-м метром. Но есть исключения- за одним орехом ходить убыточно (проест в это время 2 ореха). Поэтому решаем в таком случае (когда их 2001 или 1001) бросить этот орех (как и в Вашем решении). Таким образом, вполне строго доказуема формула
[math]
(такие скобки означают округление вверх до ближайшего целого) на множестве "осторожных" стратегий, а значит и везде.
И дальше кусочно решается явно, ответ [math]

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Исследование операций (хомячных)

Сообщение zykov » 02 апр 2020, 12:31

Ian писал(а):Source of the post Из любых его разумных действий -простой перестановкой во времени можно получить такие, и значит ответ не изменится от этого уточнения.

Это надо ещё доказывать.

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

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 02 апр 2020, 14:14

Есть еще один критерий -мнение блюстителей олимпийских традиций, их несколько сотен человек. Вот член жюри видит что задача расписана больше интуитивно, чем сокращенно от полного правильного. И пишет например к Вашему решению красным -"а чем будет питаться хомяк пока идет пустым" -понятно что претензия небольшая но минус балл, который как раз и может сыграть.
PS. Виноват , нельзя писать это красным, у Вас предусмотрена встречная переноска и хомяк не ходит пустым. То есть нет минус балла. Но в целом "минус баллы" назначаются с такой примерно аргументацией, конструктивной, а не за малость написанного
Последний раз редактировалось Ian 03 апр 2020, 07:56, всего редактировалось 1 раз.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 02 апр 2020, 14:45

Ian писал(а):-сокращаем возможные стратегии хомяка до тех, которые гарантированно содержат искомый оптимум (точнее, выброшенные не содержат строгого оптимума), но "системны". А именно, пусть хомяк еще боится что орехи украдет другой хомяк, и держит весь запас орехов не далее метра от себя, то есть -метр вперед с орехами- метр назад пустой и все, никаких иных действий не делает. Из любых его разумных действий -простой перестановкой во времени можно получить такие, и значит ответ не изменится от этого уточнения.
Это у меня сокращенное от строгого.
1.В условии предполагается что любой отрезок пути хомяка это целое число метров, иначе не расшифровано, как ему подкармливаться когда он пронес 1000 орехов полметра и сложил. Может-ли он поесть досрочно.Считаем, что нет но считаем что целое.
2.Каждый метр пути (их n =1000) рассматриваем как отдельный путь. Между ними может : изменить ношу; изменить направление; и конечно съесть 1 орех.
3.Каждый путь описываем: номером проходимого метра; размером ноши; направлением пути.
4.В последовательности записанных путей можно произвести перестановки так, что номера проходимых метров- не убывают, направления внутри одного номера метра , естественно -чередуются. Этим гарантируется реальность пути для тела хомяка. Легко догадаться что при такой перестановке не окажется что с m-го метра несется груз, который предыдущими путями на m-й метр еще не доставлен- просто потому что весь груз на m-й метр уже доставлен
5.И только сейчас мы можем упростить (с улучшением) стратегии, имеющие встречную переноску (от дома к заводу)-просто не нести этот груз, мы идем всего на метр и там питание есть точно
Остаются только "осторожные стратегии", в классе которых также строго, доказуема рекуррентная формула.
Когда я чувствую запас времени на олимпиаде- я все это пишу на всякий случай.
Это как теорема что график любой BMO- непрерывной функции можно порезать на куски и переставить их, чтобы она стала сначала возрастающей, потом убывающей. А я наоборот увеличил "осцилляцию хомяка" максимально.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Исследование операций (хомячных)

Сообщение zykov » 03 апр 2020, 16:38

Ian писал(а):Source of the post В условии предполагается что любой отрезок пути хомяка это целое число метров, иначе не расшифровано, как ему подкармливаться когда он пронес 1000 орехов полметра и сложил. Может-ли он поесть досрочно.Считаем, что нет но считаем что целое.

Думаю тут можно проще.
Сколько в сумме метров он прошел, столько орехов и съел.
Отсюда и минимизация полного пройденного пути.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Исследование операций (хомячных)

Сообщение zykov » 03 апр 2020, 16:58

Вообще моё мнение, что тут в плане строго доказательства основная сложность в обоснованном ограничении всех возможных действий на узкий круг действий которого достаточно для максимизации запаса.
В этом плане, что моё решение (с тремя интервалами - где расход 5 орехов на метр, 3 ореха на метр и 1 орех на метр), что это другое решение с шагами по 1 метру, практически одинаковые. Собственно, разница там не велика, если учесть лемму, что расход орехов одинаковый, если мы переносим на один интервал всё сразу (делая например 5 переходов) или если мы переносим на это расстояние за несколько шагов по меньшим интервалам (на каждом маленьком интервале делая те же 5 переходов).
На мой взгляд, конструкция с тремя интервалами проще, чем конструкция с шагами по 1 метру. Хотя бы потому что она короче.

Что до обоснованного ограничения всех возможных действий, то оно конечно не сложно. Но как-то длинно и муторно, если всё делать строго. Много вариантов придется перебрать. Хотя с другой стороны там всё интуитивно.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Исследование операций (хомячных)

Сообщение Ian » 03 апр 2020, 19:51

Многие похожие задачи , даже с большим количеством вариантов, можно решать принципом Беллмана: с любой позиции мы действуем оптимально, как если бы эта позиция была начальной. Это строгая теорема.
Применяется так:Рассмотрим задачи, решаемые за один проход хомяка, и запишем выигрыш как функцию от позиции (где хомяк и каждый орех лежат)
Далее, на 2-м шагу, рассмотрим все задачи, которые за 1 проход хомяка сводятся к уже рассмотренным, и там попробуем найти выигрыш как функцию от позиции, используя предыдущую функцию. Теоретически Ваше решение всего в 9 шагов и найдется первым (то есть нам уже на 9-м шагу попадется среди возможных та позиция, которая дана в условии). Но для проверки оптимальности шаги придется продолжать почти до 2500 шагов, до моего решения, последнего из оптимальных)


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 6 гостей