Enigma 1732

Spoiler for New Scientist Enigma 1732: “Cache up front” (Follow the link to see the puzzle.)

For some reason I had a really hard time getting my head around this Enigma. Even after seeing a solution posted elsewhere, it gave me trouble. I think I’m starting to get it, though.

Imagine you’re nearly done with this project; you’ve deposited one or more caches along the way, you’re at the last of these caches (call it C1), and you want to go to the Pole. In order to optimize the process you want to have the full complement S = 240 miles’ worth of supplies when you leave each cache on the way out, and you want not to have any supplies left when you reach each cache on the way back. That means you want the last cache to be 120 miles from the Pole. (Call this distance a0.) Of course this is the only time you have to cover the a0 leg.

But to get to C1 you had to leave the second to last cache (C2), a distance a1 from C1, with S supplies and arrive at C1 with S–a1. To get to the pole, then, you need to pick up a1 supplies from C1 (to get back up to S), and to get back to C2 on returning you will need to leave a1 supplies behind at C1. That means there must be a cache of 2a1 supplies at C1.

How did that cache get there? The most economical way is to have previously left C2 with supplies, dropped 2a1 at C1, and returned to C2, arriving back there empty handed. You consumed or dropped off 4a1 supplies altogether, which must make one full load S, so a1S/4 = 60 miles. You’ll cover the a1 leg twice, once to drop the cache and once to get to the pole.

But to get to C2 you had to leave the third to last cache (C3), a distance a2 from C2, with S supplies and arrive at C2 with S–a2. To get to C1 twice, then, you need to pick up a2 supplies from C2 (to get back up to S), go to C1 and and drop the cache there and return, pick up S supplies at C2, go to C1, use the cache there to go to the pole and return, and to get back to C3 on returning you will need to leave a2 supplies behind. That means there must be a cache of S+2a2 supplies at C2.

How did that cache get there? The most economical way is to have previously left C3 with supplies, dropped S/2+a2 at C2, and returned to C3, arriving back there empty handed, and then do the same thing again. You consumed or dropped off S+6a2 supplies altogether, which must make two full loads 2S, so a2 = S/6 = 40 miles. You’ll cover the a2 leg three times: twice to drop the cache at C2, once to get to the pole (via two trips on the a1 leg and one on the a0).

You’re way ahead of me, right?

But to get to C3 you had to leave the fourth to last cache (C4), a distance a3 from C3, with S supplies and arrive at C3 with S–a3. To get to C2 three times, then, you need to pick up a3 supplies from C3 (to get back up to S), go to C2 and and drop half the cache there and return, pick up S supplies at C3, go to C2 and and drop half the cache there and return, pick up S supplies at C3, go to C2, use the cache there to go to the pole and return, and to get back to C4 on returning you will need to leave a3 supplies behind. That means there must be a cache of 2S+2a3 supplies at C3.

How did that cache get there? The most economical way is to have previously left C4 with supplies, dropped (2S+2a2)/3 at C3, and returned to C4, arriving back there empty handed, and then do the same thing twice again. You consumed or dropped off 2S+8a3 supplies altogether, which must make three full loads 3S, so a3 = S/8 = 30 miles. You’ll cover the a3 leg four times: three to drop the cache at C3, once to get to the pole (via three trips on the a2 leg, two trips on the a1 leg, and one on the a0).

So where are we now? a0+a1+a2+a3 = 240/2 + 240/4 + 240/6 + 240/8 = 120 + 60 + 40 + 30 = 250 miles — so in fact C4 isn’t a cache at all but the starting point. And how far do we have to walk? 120 x 2 miles once, 60 x 2 miles twice, 40 x 2 miles three times, and 30 x 2 miles four times, or 240 + 240 + 240 + 240 = 960 miles. Or to get that answer a different way, you left the starting point four times carrying 240 miles’ worth of supplies each time, so the total walking distance was 4 x 240 miles.

Obviously (well, now it’s obvious) you can start from 240/10 miles further away (274 miles) if you use a fourth cache, 240/12 miles further than that (286 miles) using a fifth cache, and so on; 120 ∑i=1n+1(1/i) for n caches. The sum is ≈ ln(n+1) + 0.5772156649 so to go distance x requires about exp(x/120–0.5772156649)-1 caches; you can go any distance, but for instance 1000 miles requires about 2336 caches and you’d have to walk about 561,000 miles.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s