FC. Cool Clear Water
In the fourth Math Factor segment, airing February 15, 2004, we posed a question much like the later Bananas and Rockets puzzle. How do we cross the infernal desert with limited supplies of water, but unlimited porters?
(We open with the theme to Bonanza and go out with a rendition of Cool Clear Water by the immortal Marty Robbins)
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Sean Mc said,
March 8, 2009 at 12:01 am
I’m not sure exactly what number you came up with in your solution to the challenge problem. I think it was something like 1,096.
I get 729, which is 3^6.
So at mile 0, you have 729 porters;
At mile 1, you have fully-loaded 243 porters and 243 extra days of water;
At mile 2 you have 81 fully-loaded porters and 81 extra days of water;
At mile 3 you have 27 fully-loaded porters and 27 extra days of water;
At mile 4 you have 9 fully-loaded porters and 9 extra days of water;
At mile 5 you have 3 fully-loaded porters and 3 extra days of water;
At mile 6 you have 1 fully-loaded porter and 1 extra day of water;
At mile 7 you have no porters, but can make it 3 miles on your own.
strauss said,
March 8, 2009 at 12:15 am
You know, I think you’re right. Undoubtedly then the solution we gave is the sum 3^6+3^5+…+1 (Of course it’s been a few years, so I don’t recall the thinking of the time)
[EDIT]
No, wait a second, let’s think this through. I think you’re missing that the porters can’t just die of thirst out there but have to have water left along the return route (What kind of a madman ARE you?!!)
Before getting started, remember that the geometric series 3^(n-1) + … + 3 + 1 = (3^n – 1)/2
Suppose we need to go 3 days; that’s easy, just go by yourself.
4 days isn’t too bad with one porter:
Five days starts to get tricky; we need a minimum of four porters:
What’s happening is that the 3^n are supporting the efforts of the all the others.
How many porters will it take to go 6? Well, we need to get five people to day 1 with full loads of water. Moreover, we need to have water waiting for the four of those people who will be heading back that way thirsty. So nine more porters will be needed, just to deliver water to that point, for a total of 13 porters and the 1 journeyer.
How many people will be needed to go 7 days? Same analysis: we need 14 people to be fully loaded after one day, and a cache of 13 days water ready for the thirteen people who will return. So we need 27 porters just to deliver this extra water and return home themselves. Total of 40 = 27 + 9 + 3 + 1 porters, plus the one person who heads to the end.
Etc. Inductively we see that to go N+4 days, we need 1+3+…+3^(N-1) = (3^N – 1)/2 porters. For suppose we need (3^(N-1) – 1)/2 porters to go N+3 days. Then we need (3^(N-1) – 1)/2 + 1 porters to deliver enough water so everyone is fully stocked after one day, and another (3^(N-1) – 1)/2 porters to leave a day’s worth of water for the returnees.
So we will need an additional (3^(N-1) – 1)/2 + (3^(N-1) – 1)/2 + 1 = 3^(N-1) porters; adding these to the (3^(N-1) – 1)/2 we’re already bringing along we have (3^N – 1)/2. qed
Thanks!
Sean Mc said,
March 9, 2009 at 1:40 am
Chaim, Thanks for the reply!!! I absolutely love the show.
I think that my answer did account for water for the return trip, though I did discover that my answer contained another small error that would have left several hundred dead of thirst. Let me try to explain why I think my approach was basically correct, and also make the necessary correction.
First, let’s define two types of travelers: Those who will be returning to the starting point (i.e., porters) and those who are on a one-way journey (I’ll call them “trekkers”).
The first step is to develop a formula for journeys of various distances with only porters – no trekkers. Since each step of the way must be retraced on the way back, it is useful to assume that at the conclusion of each step, the porter must leave one unit of water for his own return journey. This ensures that there is always enough water for each porter to retrace every step that he has taken. Therefore, the cost of a single step forward is 2 units and the cost of a backward step is 0 units. Accounting for water this way is just a matter of preference but it seems a little simpler to me.
Looking at it this way, you would require 3 porters to complete a 2-day round trip journey. I like your notation so I’ll copy it:
Day 0:
3 . .
3 . .
3 . .
Day 1:
. 1 . (plus one stored for the return)
. 1 . (plus one stored for the return)
. 1 . (plus one stored for the return)
Reallocating:
. 0 .
. 0 .
. 3 .
Day 2:
0 . .
0 . .
. . 1 (plus one unit in cache for return at each step 1 and step 2)
So, you need 3^(n-1) porters for n days of round-trip travel. As you can see from above, at day n-1, you have one fully-loaded porter. He has water stored at each of his previous stops (D_1 through D_(n-2)) so he can continue forward one more day and then return all the way home.
So, with 3^6 porters, you will have one fully-loaded porter at day 6.
With 2*(3^6) porters, you will have 2 fully-loaded porters at day 6.
From here you have already shown that with 2 fully-loaded travelers, one can advance 4 days on a one-way journey (the trekker) while the other one turns around after a day (the porter). So two fully-loaded travelers at day 6 is sufficient to get one of them to the 10-day point.
So my answer is 2*(3^6) = 1428. Since one of these travelers is a trekker rather than a porter, you need 1427 porters to complete a 10-day one-way journey.
Sean Mc said,
March 9, 2009 at 1:45 am
Sorry, working without a calculator. 2*(3^6) -1 = 1457
Sean Mc said,
March 9, 2009 at 2:10 am
Oops. I made the exact opposite error I made the first time. Now the trekker will have 6 extra units of water stored that never get used since he doesn’t head back (one unit of water stored at each of days 1 through 6).
My first answer of 729 incorrectly assumed the trekker used no water himself for the first 6 days. My second answer of 1457 incorrectly assumed the trekker stored an extra 6 days of water for the return journey. So its starting to look like your answer of 1093, which is right in between is correct.
pamdemonia said,
March 31, 2009 at 12:32 am
I just discovered your podcast, and was working through various problems, and was glad to discover that I got this one right! my general solution looks a little different, however (brute-forced the 4, 5, and 6 day solutions, then looked for a pattern). It is the summation from 4 to i=n (n being the number of days of the journey) of 3^(i-4). so for n=5 we would have
3^(4-4) + 3^(5-4) = 3^0 + 3^1 = 1 + 3 = 4.
Although now that I look again at what y’all were doing above, it’s the same thing. I never was very good at converting a summation to a formula.
I did, however, using my formula, come up with the answer to 10 days (1093) in a little over 45 minutes, with no calculator! And then, when listening to the answer on the next podcast, turned on my computer and found this website to point out the mistake!
of course, too late. but thank you all the same for allowing me to get all excited about math and share it with others who (hopefully) won’t give me a (virtual) look of confusion/annoyance I usually get when talking about some math thing to somebody!
pam