75. Исследование пустыни. Девять участников экспедиции (каждый на автомашине) встречаются на восточной окраине пустыни. Они хотят исследовать ее внутренние районы, двигаясь все время на запад. Каждому автомобилю полного бака (содержащего 1 галлон бензина) хватает на 40 миль пути. Кроме того, он может взять с собой еще 9 канистр бензина по галлону каждая (но не больше). Целые канистры можно передавать с одного автомобиля на другой. На какое максимальное расстояние исследователи могут проникнуть в пустыню, не создавая складов топлива, необходимого для возвращения назад
75. Девять исследователей \(A, B, C, D, E, F, G, H, J\) проезжают 40 миль, затратив на это по полному баку горючего. Затем \(A\) передает по 1 галлону остальным восьми участникам и поворачивает назад, причем у него остается 1 галлон на обратную дорогу. Остальные восемь участников едут еще 40 миль, затем \(B\) передает по 1 галлону семи другим исследователям. Двух галлонов ему как раз хватает на обратный путь. Семеро исследователей проезжают еще 40 миль, затем \(C\) передает остальным шести по 1 галлону и возвращается домой, затратив на обратный путь 3 галлона. Шестеро исследователей проезжают еще 40 миль, после чего \(D\) передает каждому по 1 галлону и возвращается назад. Пятеро оставшихся проезжают еще 40 миль, затем \(E\) дает каждому по 1 галлону и возвращается назад. Теперь уже четверо исследователей продвигаются еще на 40 миль в глубь пустыни, \(F\) раздает каждому по 1 галлону и возвращается назад. \(G, H, J\) преодолевают еще 40 миль, \(G\) дает каждому по 1 галлону и едет назад. \(H\) и \(J\) проезжают еще 40 миль, \(H\) отдает 1 галлон \(J\) и возвращается. Наконец, последний путешественник \(J\) проезжает еще 40 миль, располагая 9 галлонами на обратный путь. Таким образом, \(J\) достигает пункта, расположенного в 360 милях от начального. Это наибольшее расстояние, которое можно проехать по прямой при заданных условиях.