eklhad@ihnet.UUCP (K. A. Dahlke) (09/07/84)
<The arctic winds are blowing, whistling around your ears> There is a two-companion solution to the alaskan explorer problem. Mr. Exploror (E1) begins with two friends (E2 and E3). After the first day, E3 gives a days rations to E2 and E1, and heads home. After the second day, E2 gives a days rations to E1 and heads home. E1 can now make it to the outpost. In general, the companion survival rule seriously complicates the problem. Consider the case where self-sacrifice is acceptable. After 4/n days, En graciously divides his remaining rations among the other explorers, and dies in the bitter cold. If he travels any farther, he has wasted rations on himself. If he stops any earlier, there is excess rations that cannot be carried. Thus N explorers can send a representative 4+4/2+4/3+4/4+....+4/n units. This harmonic series grows as log(n), so it requires exponentially many sacrifices to get an explorer farther out into the tundra. The situation must be even worse without all this altruism. There might even be a limit to E0's distance, but I don't think so. Any companions that travel more than 2 days must have other companions bring them rations, to help them get home. Similarly, still other companions must bring those companions rations if they stray too far from home. I am having trouble generalizing this, but I am working on it. Is it much worse than exponential (e.g. exp(exp(distance)))?? Any suggestions? -- Karl Dahlke ihnp4!ihnet!eklhad