Puzzle of the Week for 30 November 1998: Solution

Here is a solution that requires a total of 28 tanks (22 extras), with a total distance travelled of 54000 kilometers (including the final trip around Flargg). Each step begins at S with 2 full tanks, and ends at S with no water remaining on board the vehicle (except as noted below). The diagrams show (in blue) the locations of spare (full) tanks that have been left along the route at the end of each step.
1. Use 1/2 tank to travel from S to A. Leave 1 (full) tank at A, and return to S using the remaining 1/2 tank. Total distance travelled: 2000 km.
2. Use 1/2 tank to travel from S to A. Leave 1/2 tank at A, pick up the full tank left in step 1, and continue to B, using another 1/2 tank. Leave 1 full tank at B, and return to A using the remaining 1/2 tank. Pick up the 1/2 tank left earlier and use it to return to S. Total distance travelled: 6000 km.
3. Repeat step 1. Total distance travelled: 8000 km.
4. Repeat step 2, but on arrival at B leave 1/2 tank there, pick up the full tank left in step 2, continue to C, leave a full tank there, return to B, and then continue as in step 2. Total distance travelled: 14000 km.
5. Repeat step 1. Total distance travelled: 16000 km.
6. Repeat step 2. Total distance travelled: 20000 km.
7. Repeat step 1. Total distance travelled: 22000 km.
8. Repeat step 4. Total distance travelled: 28000 km.
9. Leaving S, travel in the opposite direction to I. Leave 1 full tank there as in step 1. Total distance travelled: 30000 km.
10. Following the same pattern as in step 2, but in the opposite direction, deliver a full tank to H. Total distance travelled: 34000 km.
11. Repeat step 9. Total distance travelled: 36000 km.
12. As in step 4, but going in the opposite direction, deliver a full tank to G. Total distance travelled: 42000 km.
13. Repeat step 9. Total distance travelled: 44000 km.
14. At last, everything is ready!. Travel from S to C and exchange the empty tank and the 1/2 tank for the two full tanks left there in steps 4 and 8. Continue to G and pick up the full tank left there in step 12. Continue to I and pick up the full tank left there in step 13. Continue to S, arrriving with 1/2 tank left. Total distance travelled: 54000 km.

Can you prove that no shorter solution is possible, or can you improve on this one?

Links