Сразу после доказательства в посте 28, я придумал прямое доказательство утверждения задачи, но не знал как сделать чертёж, чтобы он выглядел не очень отпугивающе (я обьясню в чём была сложность). Сейчас попробую привести доказательство, надеюсь будет понятно (если кому-то это ваще интересно).
Допустим маршрут движения такой - 1-2-3-4-5-6-7-8-9-10-11-1. На графике на оси абсцисс (Х) откладываем пройдённое расстояние, на оси ординат (Y) откладываем количество бензина в автомобиле. При этом, если бензин кончился, мы продолжаем двигаться, количество бензина становится отрицательным, не надо этого бояться, просто представьте что рядом с нами едет заправщик и в случае необходимости мы одалживаем бензин у него. Отрицательное количество бензина в баке означает что мы задолжали бензин (отрицательный баланс), потом отдадим. Задача состоит как раз в том чтобы проехать по всему маршруту и ни разу не одолжить бензин.
Итак, в начальной точке (пункт 1), бензин=0 (отмечаем это на осиY) Затем заправляемся бензином из бочки 1 и едем до пункта 2, текущее количество безина (до заправки из бочки 2)отмечаем на оси Y (оно может быть и отрицательным), и т.д. пока не доберёмся в пункт 1. Получился следующий график.
//текст доступен после регистрации//Обратите внимание что точки 1-2 соединены на сплошной линией, а пунктиром, так как настоящий график расхода бензина будет сложнее чем пунктирная линия (после заправки сразу возрос, потом по наклонной уменьшается), но это нам неинтересно, нам нужен итог в точке 2, а пунктир - просто для наглядности.
Итак мы видим, что кое-где количество бензина было отрицательным, это значит, что, не одалживая, мы не смогли бы добраться до исходного пункта. Находим самую нижнюю точку графика ( у нас это пунт 6), начинаем новый маршрут с пункта 6.
Новый график получается так: правую часть старого графика (от 6 до 1) переносим в начало, левую часть(от 1 до 6) переносим в конец.
Ниже уровня пункта 6 мы никогда не сможем опуститься (мы его так выбирали). Но мы начинаем маршрут с него, а в начальной точке уровень бензина всегда равен 0. Значит, мы никогда не опустимся ниже 0, то есть нам не придётся одалживать бензин, и мы проделаем весь маршрут на своём.
Записан