[math-fun] Travelers through the dessert
After listening to Car Talk this weekend, I was inspired to create the following question: We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]?
Let "excess" be the amount beyond the amount required to return to base. If the group travels together for a distance of 1/3, then at that point half of the group can transfer half of their remaining supplies and completely replenish the packs of the other half, while still retaining enough to return to base. Starting at that point, the remainder of the group, each of which has excess of 2/3, can travel 1/3 of the excess distance = 2/9, at which point half of the remainder transfer enough to fill the packs of the remaining half (a quarter of the original) and return home. So, we have that the remainder of the group (after consecutive halvings) can travel 1/3 + 2/9 + 4/27 + ... -> 1. I'm not sure that that counts as non-computational, though. -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Victor Miller Sent: Tuesday, July 03, 2012 10:00 AM To: math-fun Subject: [EXTERNAL] [math-fun] Travelers through the dessert After listening to Car Talk this weekend, I was inspired to create the following question: We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Bill, That's pretty good, in that your recursion is quite simple. I may be asking for the impossible but I thought it would be nice if there was some quick a a priori argument. Similarly, in the jeep problem, is there a convincing reason why the distance that the jeep can travel as a function of n (the number of trips) goes to infinity also goes to infinity without bringing in the whole argument using the harmonic series. This would be somewhat analogous to the difference between proving that there are infinitely many primes (say using Euclid's proof -- which has a minimum of computation) and proving the prime number theorem (though the difference in difficulty here is not even close to the difference in difficulty with the problem with primes). Victor On Tue, Jul 3, 2012 at 12:24 PM, Cordwell, William R <wrcordw@sandia.gov>wrote:
Let "excess" be the amount beyond the amount required to return to base.
If the group travels together for a distance of 1/3, then at that point half of the group can transfer half of their remaining supplies and completely replenish the packs of the other half, while still retaining enough to return to base. Starting at that point, the remainder of the group, each of which has excess of 2/3, can travel 1/3 of the excess distance = 2/9, at which point half of the remainder transfer enough to fill the packs of the remaining half (a quarter of the original) and return home.
So, we have that the remainder of the group (after consecutive halvings) can travel 1/3 + 2/9 + 4/27 + ... -> 1.
I'm not sure that that counts as non-computational, though.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto: math-fun-bounces@mailman.xmission.com] On Behalf Of Victor Miller Sent: Tuesday, July 03, 2012 10:00 AM To: math-fun Subject: [EXTERNAL] [math-fun] Travelers through the dessert
After listening to Car Talk this weekend, I was inspired to create the following question:
We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let us imagine, for simplicity, that each traveller can carry enough supplies to travel three units of distance. How far into the desert can we advance a pilgrim, leaving him with a whole 3-unit supply, and returning the entire support team to base? We can get him one unit into the desert with one helper, who can just get back to base before supplies run out. Suppose we can get him n units into the desert using k people. Here is a procedure for getting him n+1 units in. Launch a double expedition, of 2k people. This safely gets 2 people n units. Now they do a one-unit transfer, leaving the pilgrim topped up (as required), but the helper has only one unit left. The helper can clearly be "rescued" by a sufficiently elaborate cascade of rescue parties departing from the base at two-time-unit intervals. For some reason I am unable to work out the exact numbers needed. Just tired, I guess. On Tue, Jul 3, 2012 at 1:34 PM, Victor Miller <victorsmiller@gmail.com>wrote:
Bill, That's pretty good, in that your recursion is quite simple. I may be asking for the impossible but I thought it would be nice if there was some quick a a priori argument. Similarly, in the jeep problem, is there a convincing reason why the distance that the jeep can travel as a function of n (the number of trips) goes to infinity also goes to infinity without bringing in the whole argument using the harmonic series. This would be somewhat analogous to the difference between proving that there are infinitely many primes (say using Euclid's proof -- which has a minimum of computation) and proving the prime number theorem (though the difference in difficulty here is not even close to the difference in difficulty with the problem with primes).
Victor
On Tue, Jul 3, 2012 at 12:24 PM, Cordwell, William R <wrcordw@sandia.gov
wrote:
Let "excess" be the amount beyond the amount required to return to base.
If the group travels together for a distance of 1/3, then at that point half of the group can transfer half of their remaining supplies and completely replenish the packs of the other half, while still retaining enough to return to base. Starting at that point, the remainder of the group, each of which has excess of 2/3, can travel 1/3 of the excess distance = 2/9, at which point half of the remainder transfer enough to fill the packs of the remaining half (a quarter of the original) and return home.
So, we have that the remainder of the group (after consecutive halvings) can travel 1/3 + 2/9 + 4/27 + ... -> 1.
I'm not sure that that counts as non-computational, though.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto: math-fun-bounces@mailman.xmission.com] On Behalf Of Victor Miller Sent: Tuesday, July 03, 2012 10:00 AM To: math-fun Subject: [EXTERNAL] [math-fun] Travelers through the dessert
After listening to Car Talk this weekend, I was inspired to create the following question:
We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tuesday 03 July 2012 22:13:43 Allan Wechsler wrote:
Launch a double expedition, of 2k people. This safely gets 2 people n units. Now they do a one-unit transfer, leaving the pilgrim topped up (as required), but the helper has only one unit left. The helper can clearly be "rescued" by a sufficiently elaborate cascade of rescue parties departing from the base at two-time-unit intervals. For some reason I am unable to work out the exact numbers needed. Just tired, I guess.
I think you're answering a different question from the original: you're allowing more helpers to be sent out after the initial expedition leaves, whereas the original question (if I understood it correctly) requires the whole team to leave together, with no further reinforcements dispatched after that. -- g
It's true. I think I'm working on the puzzle that the Car Talk guys actually posed, and Victor was discussing a simplification with the extra constraint you (Gareth) are pointing out. My apologies for any confusion. On Tue, Jul 3, 2012 at 8:24 PM, Gareth McCaughan <gareth.mccaughan@pobox.com
wrote:
On Tuesday 03 July 2012 22:13:43 Allan Wechsler wrote:
Launch a double expedition, of 2k people. This safely gets 2 people n units. Now they do a one-unit transfer, leaving the pilgrim topped up (as required), but the helper has only one unit left. The helper can clearly be "rescued" by a sufficiently elaborate cascade of rescue parties departing from the base at two-time-unit intervals. For some reason I am unable to work out the exact numbers needed. Just tired, I guess.
I think you're answering a different question from the original: you're allowing more helpers to be sent out after the initial expedition leaves, whereas the original question (if I understood it correctly) requires the whole team to leave together, with no further reinforcements dispatched after that.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think the answer to the original Car Talk puzzle does not scale, in that 2 pilgrims can reach the destination by using less than 2 times the helpers. --- spoiler alert --- Car Talk asks for delivery of 1 pilgrim a distance of 6 days travel away, and each person can carry a max of 4 days rations. I think 2 helpers are required, but one helper returns with 1 day worth of unused rations. (Alternatively, the party can depart with only 11 person-days of rations.) If the party is allowed to hide rations along the way, 3 helpers can deliver 2 pilgrims, a delivery rate of 2/5 that is > 1/3. 5 depart fully loaded. After 1 day, there are 15 person-days of rations left. The next morning, 2 pilgrims and 1 helper continue forward, each fully loaded. 2 helpers return to base, each with 1 day of rations. And 1 day of rations is hidden at the overnight location. It seems like there should be some parameters that would lead to helpers turning back, and/or stashing rations, at fractional days distance, but I don't see an example case. -- Mike
Solutions scale as expected in Victor's reformulation of the problem -- instead of fixing destination distance, ask for L(n) = how far n travelers can get 1 pilgrim. If we generalize to all rationals>1 (how far can n travelers get k<n pilgrims?), what continuity properties does L(n/k) and its derivatives have? - Scott -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Michael Beeler Sent: Thursday, July 05, 2012 9:50 AM To: math-fun Subject: Re: [math-fun] [EXTERNAL] Travelers through the dessert I think the answer to the original Car Talk puzzle does not scale, in that 2 pilgrims can reach the destination by using less than 2 times the helpers. --- spoiler alert --- Car Talk asks for delivery of 1 pilgrim a distance of 6 days travel away, and each person can carry a max of 4 days rations. I think 2 helpers are required, but one helper returns with 1 day worth of unused rations. (Alternatively, the party can depart with only 11 person-days of rations.) If the party is allowed to hide rations along the way, 3 helpers can deliver 2 pilgrims, a delivery rate of 2/5 that is > 1/3. 5 depart fully loaded. After 1 day, there are 15 person-days of rations left. The next morning, 2 pilgrims and 1 helper continue forward, each fully loaded. 2 helpers return to base, each with 1 day of rations. And 1 day of rations is hidden at the overnight location. It seems like there should be some parameters that would lead to helpers turning back, and/or stashing rations, at fractional days distance, but I don't see an example case. -- Mike _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, in that problem, you can have the first helper go for 1 day, distribute 1 day's worth to the other two left, and turn back. After another 1 1/2 days, the remaining helper gives 1 1/2 days rations to the pilgrim and turns back, who then can travel for 6 1/2 days in total (more than enough). This is the maximum distance with two helpers. If there is only one helper, the best he can do is to go for 4/3 of a day, and give 4/3 to the pilgrim and turn back. But then the pilgrim can only go 5 1/3 days in all, which is easy to see is a maximum. On Thu, Jul 5, 2012 at 12:49 PM, Michael Beeler <mikebeeler@verizon.net>wrote:
I think the answer to the original Car Talk puzzle does not scale, in that 2 pilgrims can reach the destination by using less than 2 times the helpers.
--- spoiler alert ---
Car Talk asks for delivery of 1 pilgrim a distance of 6 days travel away, and each person can carry a max of 4 days rations. I think 2 helpers are required, but one helper returns with 1 day worth of unused rations. (Alternatively, the party can depart with only 11 person-days of rations.)
If the party is allowed to hide rations along the way, 3 helpers can deliver 2 pilgrims, a delivery rate of 2/5 that is > 1/3. 5 depart fully loaded. After 1 day, there are 15 person-days of rations left. The next morning, 2 pilgrims and 1 helper continue forward, each fully loaded. 2 helpers return to base, each with 1 day of rations. And 1 day of rations is hidden at the overnight location.
It seems like there should be some parameters that would lead to helpers turning back, and/or stashing rations, at fractional days distance, but I don't see an example case.
-- Mike
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
On Tuesday 03 July 2012 16:59:43 Victor Miller wrote:
We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]?
Answer 1: The travellers don't need rations because they can just eat some of the dessert, and therefore L[n] is very large :-). Answer 2: Suppose we have a plan that gets the pilgrim to a certain distance with a certain quantity of rations before the last helper has to leave. By "copying" all the helpers many times, we can give the pilgrim more rations, up to the point at which he has a full day's rations when the last helper leaves (and more, which he can't take because of the carrying limit). (Nitpick: Not if all the helpers leave at a point where they have *exactly* enough rations left to return home. Therefore, consider only plans that leave everyone with a strictly positive amount of slack.) And by replacing each helper with a copy of the plan that puts that helper in the role of pilgrim, we can get all the helpers to their final destinations with a full day's rations or more. So if the last helper leaves at a distance 1-h from home with h>0, by doing this we can get them to at least 1-h/2. From all of which it follows, unless I'm all mixed up, that there's a plan attaining any distance < 2 days from home. -- g
participants (6)
-
Allan Wechsler -
Cordwell, William R -
Gareth McCaughan -
Huddleston, Scott -
Michael Beeler -
Victor Miller