Friday Puzzler -- Trek to the North Pole

Re: Friday Puzzler -- Trek to the North Pole

Larry Barrett

Here is an approach for simpler, but essentially the same, problem.

Suppose you have unlimited supplies at Point A, the goal is at Point E, 4 miles from A, and you can carry 3 miles of supplies. How many miles must you travel to get to E and return to A, stockpiling supplies at points B, C, and D, (1, 2, and 3 miles, respectively, from A)?

Step 1. Travel from A to B, drop 1 mile of supplies, return to A; supplies at B=1.

Step 2. Repeat step 1; supplies at B=2.

Step 3. Travel from A to B, reload with 1 mile of supplies (reload 1 for short), travel to C, drop 1 mile of supplies (drop 1 for short), return to B, reload 1, return to A; supplies at B=0, supplies at C=1. Miles traveled for steps 1, 2, 3 = 8.

Steps 4, 5, 6: Repeat steps 1, 2, 3. Supplies at B=0, supplies at C=2. Miles traveled for steps 1-6=16.

Step 7 and 8: Repeat steps 1 and 2. Supplies at B=2, supplies at C=2. Miles traveled for steps 1-8=20.

Step 9. Travel from A to B, reload 1, travel to C, reload 1, travel to D, drop 1, return to C, reload 1, return to B, reload 1, return to A. Supplies at B=0, supplies at C=0, supplies at D=1. Miles traveled for steps 1-9=26.

Steps 10-17: Repeat steps 1-8. Supplies at B=2, supplies at C=2, supplies at D=1. Miles traveled for steps 1-17= 46.

Step 18 (final step, I think): Travel from A to B, reload 1, travel from B to C, reload 1, travel from C to D, reload 1. At this point you have 1 mile to go to reach E, and 3 miles of supplies, so you travel from D to E, return to C, reload 1, travel from C to B, reload 1, travel from B to A. Supplies at B, C, D, E=0. Total miles traveled =54.

Or, build a slightly bigger sled and travel just 8 miles.

  Not there yet

Alex Y

Similar, but not the same. I think your solution is probably optimal for the case you gave, but that strategy, extended to the given problem, will not give you an the shortest cumulative mileage.

Closer to optimal

Alex Y

Larry, I said I suspected your solution was close to optimal for your 4-mile 3-capacity sled model. But I was way wrong.

Here's a solution traveling only half the miles you did, and it's still not optimal:

I establish stockpiles at four points:

A is 1/2 mile from base camp

B is 1.25 miles from base camp

C is 1.75 miles from base camp

D is 2.5 miles from base camp.

Here are the trips I take:

Trips 1-3: A, drop 2 ( "Ad2"), return.

After trip three:Three miles traveled ("3mi", 6 miles' supply at A ("A6")

Trips 4-6: A, pick up 1/2 ("Ap1/2"), Bd1.5, Ap1/2, return

After trip 6: 10.5mi, A3, B4.5

Trip 7: Ap.5, Bp.75, Cd2, BP.75,Ap.5, return

After trip 7: 14mi, A2, B3, C2

Trip 8: Ap.5, Bp.75, Cp.5, Dd1.5 , Cp.5, BP.75,Ap.5, return

After trip 8: 19mi, A1, B1.5, C1, D1.5

Trip 8: Ap.5, Bp.75, Cp.5, Dp.75, Goal!, Dp.75, Cp.5, BP.75, Ap.5, return

After trip 9: 27 miles, goal reached, no stores left.

Re: Closer to optimal and a question

Larry Barrett

Alex, thanks for the new info. I did not think my first cut would be optimal (did not know one way or the other). It was just a first try to see if some more general approach might be deduced from a simpler problem. I also assumed stockpiles had to be a whole mile points. So your new approach helps for sure. I do not have any better idea yet, but will continue to think. In your problem, are stockpiles allowed anywhere on the continum from 0-250 miles?

Re: Closer to optimal and a question

Alex Y

Yes, stockpiles can be anywhere along the route.

They happen to be at integral mileposts, but that is not a condition.

Re: Closer to optimal and a question

Larry Barrett

Been too busy to work on solution, but have some thoughts.

Designate the goal as N, and stockpile points as Na, Nb, Nc, ..., and the last stockpile point as Nz (not meant to imply there are 26).

If the goal is N and the sled has a capacity of C, the last stockpile point Nz is determined by (N -C/2). This assumes that the sled is topped off at each intermediate stockpile point, so that when it leaves Nz it is full and uses half the capacity getting to N and the other half getting back to Nz. For my simple problem (which may not be any simpler than the original problem), N=4, C=3, and Nz=2.5, which is what Alex used in his solution, which is still not optimal. For the original problem, N=250, C=240, so Nz=250-120 = 130.

Before the last trip the sum of the supplies at the stockpile points, plus the sled capacity is equal to twice the distance to the goal, and therefore the sum of the supplies at the stockpile points is equal to the sled capacity.

Symmetry suggests that on the last trip, on the outbound leg the sled tops off with half of the supplies at each stockpile point, and on the inbound leg it tops off with the remaining half. This is true for Alex's improved solution, but was not true in my first attempt.

Progress report

Alex Y

Your points are all on-target (and productive), except the conclusion reached below:

Before the last trip the sum of the supplies at the stockpile points, plus the sled capacity is equal to twice the distance to the goal, and therefore the sum of the supplies at the stockpile points is equal to the sled capacity.

Re: Friday Puzzler -- Trek to the North Pole

bill earl

The total number of miles is 1000 - 10 times the number of round trips.

Once I turned the problem around, the solution was easier than I thought.

Close, but not quite

Alex Y

That is very good, but you can do a little better. Just curious: where are your storage points?

I'm surprised you got as close to the minimum as you did, with as many trips as you planned. Would you mind giving that solution?

Re: Close, but not quite

bill earl

Start with a 60 mile round-trip - dropping 6 units of supplies every mile on the way out.

Next a 140 mile round trip - picking up one unit of supplies each mile for the first 30 and last 30. Dropping 4 units of supplies on the way out every mile beyond 30.

Then a 260 mile round trip - picking up one unit of supplies each mile for the first and last 70 miles. Dropping 2 units of supplies on the way out every mile beyond 70.

Finally a 500 mile round trip - picking up one unit of supplies each mile for the first and last 130 miles.

130 stockpiles in total.

That's it!!

Alex Y

Four trips and 960 miles.

Good job.

BTW, if you don't want to be stopping every mile, you can just dump supplies at the far point of each trip, reserving enough for the first leg homeward. Then going out, top up the sled at each supply point before the end and coming back, pick up just enough to reach the next supply point.

I'm still curious about your "almost" solution with ten trips and 1,000 miles.

And please share the way you looked at it in reverse to solve it.

Re: That's it!!

bill earl

Not 10 trips. I said "10 times the number of round trips." (10x4 = 40)

I started by calculating that I needed 240 units of supplies at mile 130 to make the final push from the pole.

To get there and back with 240 units, I would need 2 units per mile stockpiled along the way. Assuming I could get 240 units to the 70 mile mark, I would have enough to salt the 60 miles from there to mile 130 with 2 units per mile.

Working back from there, I would need 2 units per mile, plus the 2 units for the final trip. So I needed to work out how far I could go while stashing 4 units per mile. That took me back to the 30 mile mark

And from the 30 mile mark back I would need to stash 6 units per mile. 240 units would be exactly enough to do that from home base.

Re: That's it!!

Alex Y

Nicely done!

I read your answer of "1,000 minus 10 times the number of trips" as "1,000 dash [that is]10 times the number of trips", and in my mind, figuring that 10 x 10 = 1,000 took it that you were making 10 trips. And I can't even get off by saying it was before my first cup of coffee!

Another back-solve for this one

Alex Y

Bill has presented an excellent rationale, working backwards, for the solution to this problem. I have seen another "solution" along the same lines, which I did not find intuitive. I present it here in case someone else finds it helpful.

Consider a reverse problem, where you start at the North pole, and take on two units of supplies for each mile you travel.

After 120 miles, your sled will be full, and you will have to get a second sled to keep picking up the supplies. But with two sleds, you are now picking up 4 units of supplies every mile, so can only make it 60 miles before the second sled is full.

At that point, add a third sled to store everything you are picking up. At 6 units per mile, that sled gets filled up in 40 miles.

Adding one more sled, and now picking up 8 units per mile, you are able to make it the last 30 miles to base camp.

I see why this works, and why it gives the answer to the original question, but as i said, I do not find this an intuitive way to look at the problem, while Bill's solution is.

The four-trip problem given is the simplest one. 1+1/2+1/3+1/4=50/24, the length of the total targeted round trip divided by the capacity of the sled. 1+1/2+1/3 <2, so you could make the trip in a single round trip.

Larry: Turns out your "simplified" solution was not simpler after all. To get to a round trip of 8 miles with a sled carrying only 3 units, you would segments of 1/2 sled capacity * (1,1/2,1/3,1/4,1/5,1/6,1/7,1/8) and you'd have some supplies left over, which means the solution would not be unique.

Re: Another back-solve for this one

bill earl

I agree. The math is all nice and clean. But what was the reasoning behind picking up 2 units per mile to start?