Mathematics Problem

[Gautham]

Dynamic Resource Allocation - The Dynamic Well Location Problem

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 i, i=1,2, . . .   the i^th family arrives and a new well is drilled at a point from the open unit interval   (0, 1),  so that there will be i wells. The goal is to insure that after the new well is drilled, each of the i open subintervals   (0, 1/i),   (1/i, 2/i),   . . .,   ((i-1)/i, 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.