Андрей посадил 8 деревьев в ряд на расстоянии 5 метров друг от друга. Рядом с первым деревом есть колодец. Для поливки двух деревьев нужно одно ведро воды. Какой наименьший путь надо преодолеть Андрею, чтобы полить все деревья, пользуясь одним ведром? 80 105 125

Ответ: 125 м.

Разберёмся, как минимизировать путь. Ведро хватает ровно на два дерева, значит нужно 4 «рейса» от колодца (который у первого дерева). Возвращаться к колодцу для пополнения нужно после каждого из первых трёх рейсов; после последнего — возвращаться уже не обязательно (полив завершён). Поэтому выгодно оставить самые дальние деревья на последний рейс, чтобы не делать лишний обратный путь.

Деревья стоят через 5 м: их расстояния от колодца — 0, 5, 10, 15, 20, 25, 30, 35 м.

Оптимальный план:

• 1-й рейс: полить деревья на 0 и 5 м. Пройти 5 м туда и 5 м обратно: 10 м.

• 2-й рейс: полить на 10 и 15 м. Пройти 15 м туда и 15 м обратно: 30 м.

• 3-й рейс: полить на 20 и 25 м. Пройти 25 м туда и 25 м обратно: 50 м.

• 4-й (последний) рейс: полить на 30 и 35 м. Пройти только 35 м в один конец: 35 м.

Суммарно: $10 + 30 + 50 + 35 = 125$ м.

Почему лучше не получится: при любом планировании первые три рейса требуют возвращения к колодцу, и их «цена» равна удвоенному расстоянию до более дальнего из поливаемых в рейсе деревьев. Чтобы эта сумма была минимальна, в первые три рейса берём попарно ближайшие к колодцу деревья, а самые дальние (30 и 35 м) оставляем на последний рейс без возвращения.

Итак, минимальный путь — 125 м.