4 ms·

The keys that makes the desert problem finite bounded are "can't leave supplies in the desert to pick up later" and "without starving any traveler on the way".

The keys that makes the desert problem finite bounded are "can't leave supplies in the desert to pick up later" and "without starving any traveler on the way". Relax either restriction and you're back to exponential behavior, either by taking extra trips or leaving a lot of dead travelers.

Someone 4y ago
I don’t see how that matters if you can have arbitrarily many carriers. Let’s say a carrier carries food for 3 days. To get one carrier 4 units out, send out 2 carriers, let them walk for one day, have one of them load up the other. The first has food for 1 day left and can return to base, the second has 3 days supplies and can walk to the finish. To get one carrier 5 days out, do the first part twice to get 2 carriers at distance 1 with a day of supplies and 2 with 3 days of supplies. The first two can return to base, the other two can walk to distance 2, reload, and let one carrier reach distance 5. The other has food to return to distance 1. There, it can be met by a carrier who left base just in time with 2 days rations left, and both can return to base. I think this scheme extends infinitely. To get one carrier N+1 days out, get 2 fully loaded N-3 days out, have one dash for the finish, and have one return to N days out, where they can be supplied with one day’ rations to return to N-1 days, etc. (Given the description of https://puzzling.stackexchange.com/questions/233/travellers-across-a-desert https://puzzling.stackexchange.com/questions/233/travellers-... and https://www.mathsisfun.com/puzzles/cars-across-the-desert-solution.html https://www.mathsisfun.com/puzzles/cars-across-the-desert-so..., I think “get at least one carrier across” is the correct interpretation of the somewhat imprecise text on Wikipedia. It certainly can’t be “get all across”, as that’s trivial if you don’t allow intermediate dumps)

Someone 4y ago

I don’t see how that matters if you can have arbitrarily many carriers. Let’s say a carrier carries food for 3 days. To get one carrier 4 units out, send out 2 carriers, let them walk for one day, have one of them load up the other. The first has food for 1 day left and can return to base, the second has 3 days supplies and can walk to the finish. To get one carrier 5 days out, do the first part twice to get 2 carriers at distance 1 with a day of supplies and 2 with 3 days of supplies. The first two can return to base, the other two can walk to distance 2, reload, and let one carrier reach distance 5. The other has food to return to distance 1. There, it can be met by a carrier who left base just in time with 2 days rations left, and both can return to base. I think this scheme extends infinitely. To get one carrier N+1 days out, get 2 fully loaded N-3 days out, have one dash for the finish, and have one return to N days out, where they can be supplied with one day’ rations to return to N-1 days, etc. (Given the description of https://puzzling.stackexchange.com/questions/233/travellers-across-a-desert https://puzzling.stackexchange.com/questions/233/travellers-... and https://www.mathsisfun.com/puzzles/cars-across-the-desert-solution.html https://www.mathsisfun.com/puzzles/cars-across-the-desert-so..., I think “get at least one carrier across” is the correct interpretation of the somewhat imprecise text on Wikipedia. It certainly can’t be “get all across”, as that’s trivial if you don’t allow intermediate dumps)