Dynamic Resource Allocation, Planning for Growth

Dynamic Resource Allocation - The Dynamic Well Location Problem

Here is a problem that you may have fun working on. This problem originally arose as a resource allocation problem in parallel computing that someone else was trying to deal with, where the number of users kept increasing. However, I've restated it in a simpler context. Ann Arbor, and other cities, faces an even harder dynamic location problem: where should they locate schools or fire stations, given that the population keeps increasing?

Consider the following process, which goes on in stages:

A community is building a series of wells, trying to space them to meet the growing demand. Whenever a new family joins the community, the other families move a bit to make room for the new one, and everyone ends up with the same amount of room. Fortunately, they all live on the open interval (0,1). Unfortunately, the wells can't move.
Initially there is no well. At each stage k, k=1,2, . . . the k^th family arrives and a new well is drilled at a point from the open unit interval (0, 1), so that there will be k wells. The goal is to insure that after the new well is drilled, each of the k open subintervals (0, 1/k), (1/k, 2/k), . . ., ((k-1)/k, 1) contains exactly one well.
For example, suppose the following choices were made.

Stage 1: first well is drilled at 0.7. Then certainly the interval (0, 1) , corresponding to a single family being in the community, has a well.
Stage 2: a second family arrives, and a second well is drilled at 0.3. Now each of (0, 1/2) and (1/2, 1) has a well.
Stage 3: third well is drilled at 0.4. Now each of the three families, residing in (0, 1/3), (1/3, 2/3), and (2/3, 1) , has a well.
Stage 4: Oops, there is no place to correctly drill the fourth well, because (1/4, 2/4) already has two wells and hence no matter where the fourth well is placed, one family will be without a well.
However, if the second well had been put at 0.2, then it would have been possible to complete the fourth stage.

Can this process go on forever? Provide a proof.

If it can go on forever, then how should the locations be chosen? (There may not be a unique answer.)

If it cannot go on forever, what is the longest it can go?

There are several ways to modify the problem. For example, you can allow wells to be at the boundaries of the open intervals and assign them to be in one (but not both) of the intervals it bounds. Thus if the first well had been at 0.5, in the second stage we could decide, say, to allocate the well to (0, 1/2) and put the second well in the interval (1/2, 1). You could also make the interval a circle, which would correspond to the region being a circular disk and each family getting a fair slice.

I know the answer to this problem, but there are several interesting related ones where I don't know the answer, and for some of them I'm not even sure of what the most interesting question is.