Added By: Feedage Forager | |
Language: | |
Tags: | |
day days water days extra days extra fully loaded fully loaded porters loaded mile fully porters return water mile water | |
Rate this Feed |
Comments (0) |
Feed Details and Statistics |
Last Build Date: Fri, 08 Aug 2014 12:52:06 +0000
Tue, 31 Mar 2009 06:32:32 +0000
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! pamMon, 09 Mar 2009 08:10:40 +0000
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.Mon, 09 Mar 2009 07:40:57 +0000
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.Sun, 08 Mar 2009 06:15:44 +0000
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.3 . . . . 2 . . . . 1 . . . . Victory!4 days isn't too bad with one porter:
3 . . . . 3 . . . . . 2 . . . . 2 . . . (transferring water:) . 1 . . . . 3 . . . 0 . . . . . . 2 . . etcFive days starts to get tricky; we need a minimum of four porters:
3 . . . . . 3 . . . . . 3 . . . . . 3 . . . . . 3 . . . . . . 2 . . . . . 2 . . . . . 2 . . . . . 2 . . . . . 2 . . . . . 1 . . . . . 1 . . . . . 2 . . . . . 3 . . . . . 3 . . . . 0 . . . . . (these three go back home) 0 . . . . . 0 1 . . . . (but a cache has been left) . . 2 . . . . . 2 . . . 0 . . . . . 0 . . . . . 0 1 . . . . . . 1 . . . (now this guy can make it back home) . . 3 . . . (and this one can head off to the end)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!
Sun, 08 Mar 2009 06:01:57 +0000
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.