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