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