Чтобы выжить зимой, жадный голодный хомяк решил ограбить ореховый заводик, находящийся в 1000 м от его норы. На заводике осталось 3000 орехов. В щеки хомяка помещается максимум 1000 орехов. Куда и с чем бы ни шел хомяк, каждый метр ему необходимо подкрепляться 1 орехом. Хомяк уже на заводике и опасен. Какое максимальное число орехов он сможет запасти?
Надо не забыть, что холостой метр тоже требует ореха
Исследование операций (хомячных)
Исследование операций (хомячных)
Ему надо набрать 1000 орехов, отнести их на какое-то расстояние (менее 500м), там часть выложить, оставив у себя ровно столько, чтобы вернутся на завод. И так ещё 2 раза, пока на заводе не кончатся орехи. Этот участок он пройдёт 5 раз. Значит истратит орехов.
Потом так же переносить от этой точки до другой. Если на первой точке было более 2000 орехов, то 5 раз нужно пройти. Если от 1001 до 2000, то 3 раза. Если не более 1000, то уже можно 1 раз пройти.
Понятно, что желательно, чтобы суммарное расстояние, где тратится по 5 проходов, было минимизировано.
Т.е. первая должна быть 200м. Он истратит 1000 орехов и ему нужно будет перенести 2000 орехов на расстояние 800м.
Далее, должно быть 333м. Он истратит 999 орехов и ему нужно будет перенести 1001 орех на расстояние 467м.
Оставшееся расстояние он проходит один раз. Один орех придется выбросить, т.к. влезает только 1000.
Истратит он 467. Запасено будет 1000-467=533 ореха.
Потом так же переносить от этой точки до другой. Если на первой точке было более 2000 орехов, то 5 раз нужно пройти. Если от 1001 до 2000, то 3 раза. Если не более 1000, то уже можно 1 раз пройти.
Понятно, что желательно, чтобы суммарное расстояние, где тратится по 5 проходов, было минимизировано.
Т.е. первая должна быть 200м. Он истратит 1000 орехов и ему нужно будет перенести 2000 орехов на расстояние 800м.
Далее, должно быть 333м. Он истратит 999 орехов и ему нужно будет перенести 1001 орех на расстояние 467м.
Оставшееся расстояние он проходит один раз. Один орех придется выбросить, т.к. влезает только 1000.
Истратит он 467. Запасено будет 1000-467=533 ореха.
Исследование операций (хомячных)
А например доказательство что нельзя запасти больше?
Исследование операций (хомячных)
Там вроде как очевидно.
Если меньше 200м, то либо ещё ходить 5 раз - тут всё равно важно суммарное расстояние, либо начинать ходить по 3 раза (заберем всё равно максимум 2000 орехов, остальное выбросим), но тогда расстояние будет больше 800м - значит расход будет больше.
Если больше 200м, то на каждый лишний метр тратим по 5 орехов - убыток.
Аналогично с , где ходим по 3 раза.
Если будет 334м вместо 333м, то сэкономим мы 2 ореха - выбрасывать один не надо и 1м для последнего прохода. Но теряем 3 ореха - 1м и 3 прохода.
Если меньше 200м, то либо ещё ходить 5 раз - тут всё равно важно суммарное расстояние, либо начинать ходить по 3 раза (заберем всё равно максимум 2000 орехов, остальное выбросим), но тогда расстояние будет больше 800м - значит расход будет больше.
Если больше 200м, то на каждый лишний метр тратим по 5 орехов - убыток.
Аналогично с , где ходим по 3 раза.
Если будет 334м вместо 333м, то сэкономим мы 2 ореха - выбрасывать один не надо и 1м для последнего прохода. Но теряем 3 ореха - 1м и 3 прохода.
Исследование операций (хомячных)
Вот сравните. действий у хомяка помногу в каждый момент.
Выбираем тот прием, который указан здесь 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]
Выбираем тот прием, который указан здесь 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]
Исследование операций (хомячных)
Ian писал(а):Source of the post Из любых его разумных действий -простой перестановкой во времени можно получить такие, и значит ответ не изменится от этого уточнения.
Это надо ещё доказывать.
А вообще, достаточно очевидно неформальное доказательство или нет - это субъективный критерий.
Безусловно для этой задачи можно расписать полностью формальное доказательство на несколько страниц, где однозначно проверяется - верно оно или нет. Тут правда другая проблема, что верность не будет очевидной для человека в силу большой длины этого доказательства. Но тут человека может заменить компьютер. Ведь проверка верности формального доказательства - это просто проверка на отсутствие синтаксических ошибок.
Исследование операций (хомячных)
Есть еще один критерий -мнение блюстителей олимпийских традиций, их несколько сотен человек. Вот член жюри видит что задача расписана больше интуитивно, чем сокращенно от полного правильного. И пишет например к Вашему решению красным -"а чем будет питаться хомяк пока идет пустым" -понятно что претензия небольшая но минус балл, который как раз и может сыграть.
PS. Виноват , нельзя писать это красным, у Вас предусмотрена встречная переноска и хомяк не ходит пустым. То есть нет минус балла. Но в целом "минус баллы" назначаются с такой примерно аргументацией, конструктивной, а не за малость написанного
PS. Виноват , нельзя писать это красным, у Вас предусмотрена встречная переноска и хомяк не ходит пустым. То есть нет минус балла. Но в целом "минус баллы" назначаются с такой примерно аргументацией, конструктивной, а не за малость написанного
Последний раз редактировалось Ian 03 апр 2020, 07:56, всего редактировалось 1 раз.
Исследование операций (хомячных)
Это у меня сокращенное от строгого.Ian писал(а):-сокращаем возможные стратегии хомяка до тех, которые гарантированно содержат искомый оптимум (точнее, выброшенные не содержат строгого оптимума), но "системны". А именно, пусть хомяк еще боится что орехи украдет другой хомяк, и держит весь запас орехов не далее метра от себя, то есть -метр вперед с орехами- метр назад пустой и все, никаких иных действий не делает. Из любых его разумных действий -простой перестановкой во времени можно получить такие, и значит ответ не изменится от этого уточнения.
1.В условии предполагается что любой отрезок пути хомяка это целое число метров, иначе не расшифровано, как ему подкармливаться когда он пронес 1000 орехов полметра и сложил. Может-ли он поесть досрочно.Считаем, что нет но считаем что целое.
2.Каждый метр пути (их n =1000) рассматриваем как отдельный путь. Между ними может : изменить ношу; изменить направление; и конечно съесть 1 орех.
3.Каждый путь описываем: номером проходимого метра; размером ноши; направлением пути.
4.В последовательности записанных путей можно произвести перестановки так, что номера проходимых метров- не убывают, направления внутри одного номера метра , естественно -чередуются. Этим гарантируется реальность пути для тела хомяка. Легко догадаться что при такой перестановке не окажется что с m-го метра несется груз, который предыдущими путями на m-й метр еще не доставлен- просто потому что весь груз на m-й метр уже доставлен
5.И только сейчас мы можем упростить (с улучшением) стратегии, имеющие встречную переноску (от дома к заводу)-просто не нести этот груз, мы идем всего на метр и там питание есть точно
Остаются только "осторожные стратегии", в классе которых также строго, доказуема рекуррентная формула.
Когда я чувствую запас времени на олимпиаде- я все это пишу на всякий случай.
Это как теорема что график любой BMO- непрерывной функции можно порезать на куски и переставить их, чтобы она стала сначала возрастающей, потом убывающей. А я наоборот увеличил "осцилляцию хомяка" максимально.
Исследование операций (хомячных)
Ian писал(а):Source of the post В условии предполагается что любой отрезок пути хомяка это целое число метров, иначе не расшифровано, как ему подкармливаться когда он пронес 1000 орехов полметра и сложил. Может-ли он поесть досрочно.Считаем, что нет но считаем что целое.
Думаю тут можно проще.
Сколько в сумме метров он прошел, столько орехов и съел.
Отсюда и минимизация полного пройденного пути.
Исследование операций (хомячных)
Вообще моё мнение, что тут в плане строго доказательства основная сложность в обоснованном ограничении всех возможных действий на узкий круг действий которого достаточно для максимизации запаса.
В этом плане, что моё решение (с тремя интервалами - где расход 5 орехов на метр, 3 ореха на метр и 1 орех на метр), что это другое решение с шагами по 1 метру, практически одинаковые. Собственно, разница там не велика, если учесть лемму, что расход орехов одинаковый, если мы переносим на один интервал всё сразу (делая например 5 переходов) или если мы переносим на это расстояние за несколько шагов по меньшим интервалам (на каждом маленьком интервале делая те же 5 переходов).
На мой взгляд, конструкция с тремя интервалами проще, чем конструкция с шагами по 1 метру. Хотя бы потому что она короче.
Что до обоснованного ограничения всех возможных действий, то оно конечно не сложно. Но как-то длинно и муторно, если всё делать строго. Много вариантов придется перебрать. Хотя с другой стороны там всё интуитивно.
В этом плане, что моё решение (с тремя интервалами - где расход 5 орехов на метр, 3 ореха на метр и 1 орех на метр), что это другое решение с шагами по 1 метру, практически одинаковые. Собственно, разница там не велика, если учесть лемму, что расход орехов одинаковый, если мы переносим на один интервал всё сразу (делая например 5 переходов) или если мы переносим на это расстояние за несколько шагов по меньшим интервалам (на каждом маленьком интервале делая те же 5 переходов).
На мой взгляд, конструкция с тремя интервалами проще, чем конструкция с шагами по 1 метру. Хотя бы потому что она короче.
Что до обоснованного ограничения всех возможных действий, то оно конечно не сложно. Но как-то длинно и муторно, если всё делать строго. Много вариантов придется перебрать. Хотя с другой стороны там всё интуитивно.
Исследование операций (хомячных)
Многие похожие задачи , даже с большим количеством вариантов, можно решать принципом Беллмана: с любой позиции мы действуем оптимально, как если бы эта позиция была начальной. Это строгая теорема.
Применяется так:Рассмотрим задачи, решаемые за один проход хомяка, и запишем выигрыш как функцию от позиции (где хомяк и каждый орех лежат)
Далее, на 2-м шагу, рассмотрим все задачи, которые за 1 проход хомяка сводятся к уже рассмотренным, и там попробуем найти выигрыш как функцию от позиции, используя предыдущую функцию. Теоретически Ваше решение всего в 9 шагов и найдется первым (то есть нам уже на 9-м шагу попадется среди возможных та позиция, которая дана в условии). Но для проверки оптимальности шаги придется продолжать почти до 2500 шагов, до моего решения, последнего из оптимальных)
Применяется так:Рассмотрим задачи, решаемые за один проход хомяка, и запишем выигрыш как функцию от позиции (где хомяк и каждый орех лежат)
Далее, на 2-м шагу, рассмотрим все задачи, которые за 1 проход хомяка сводятся к уже рассмотренным, и там попробуем найти выигрыш как функцию от позиции, используя предыдущую функцию. Теоретически Ваше решение всего в 9 шагов и найдется первым (то есть нам уже на 9-м шагу попадется среди возможных та позиция, которая дана в условии). Но для проверки оптимальности шаги придется продолжать почти до 2500 шагов, до моего решения, последнего из оптимальных)
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 4 гостей