show/hide this revision's text 2 Typos corrected: most importantly, $2k$ changed to $ 2^k$.

I'll now put forward my candidate solution to the problem. It clearly satisfies the hurdle condition, but I can't prove its optimality. To get a handle on the algorithm, let's represent $x_1$ , $x_2$ , … as hotel guests numbered accordingly. Recall Hilbert's hotel, where the unfortunate guests were ever being shunted from their room to a higher-numbered room. The hotel in this case, rather than having a countably infinite number of discrete rooms, is a continuum of “rooms”, represented by the points of a closed bounded real interval; [0 , 1.4] is big enough, as it turns out)out. The “guests”, numbered 1, 2, … , are movable tags, each assigned to a rational point in the interval. Unlike Hotel Hilbert, which is always full, this hotel starts empty apart from the proprietor who resides permanently at 0, and the guests arrive one by one in the order 1, 2, … . The proprietor operates the strict rule that, when there are a total of $m$ guests in the hotel, there must be a space of at least $1/m$ between the residents (including himself), for $m$ = 1, 2, … . Guest 1 is assigned to the point 1. Guest 2 is placed at 1/2. When guest 3 arrives, she is put at 1/3, while guests1 guests 1 and 2 are moved up by a distance 2/3 – 2/(3 + 1) = 1/6. When guest 4 comes, he is allotted to 1/2 + 1/6 + 1/4 = 11/12. The general rule is as follows. For $k$ = 1, 2, … , after $2k$ 2^k$ guests have been accommodated, the next $2k$ 2^k$ are put consecutively into the $2k$ 2^k$ spaces between the proprietor and the first $2k$ 2^k$ guests, in left-to-right order: An odd-numbered arrival, say guest $2n$ – $1$, is assigned to the point below her right-hand neighbour (guest $n$) that is 1/($2n$ – $1$) above her left-hand neighbour, while all the guests to her right are moved up by a distance 2/($2n$ – 1) – $1/n$; when the next, even-numbered, guest arrives (guest $2n$), he can just go to the midpoint of the next space up, at a distance 1/$2n$ above his left-hand neighbour (guest $n$), and mercifully no resident has to move until the next (odd-numbered) guest arrives. The result is that the guests, now identified with their limiting room positions, are each the sum of two parts: The first part is a sum of a finite number of distinct fractions of the form $1/n$, while the second is an infinite series whose terms are of the form 1/$n$($2n$ – 1), where $n$ is a positive integer. Generally an infinite number of terms of the latter type are absent; only in the case of $x_1$ is the series free of gaps, and then the first “sum” has only one term. Thus $x_1$ = 1 + ∑{1/$j$($2j$ – 1) : $j$ = 2, 3, …} = ln 4, and this is also the supremum of the sequence.

An alternative characterization, suggested by Gerhard Paseman, is as follows: For j from 2^(k-1)+1 to 2^k, you will arrange to place guest (2j-1) to the left of guest j and guest 2j to the right of guest j. Since space to the left of guest j has previously been guaranteed to be 1/j from his/her lefthand neighbor, guest (2j-1) needs more since it needs 1/(2j-1) space to his/her left and right. So add the difference delta_j = (2/(2j-1) – 1/j) to the left of guest j and shift guest j and every guest on the right of guest j by this difference delta_j. Since guest 2j does not need more than 1/j = (2/2j) space, no such adjustment is needed for guest 2j. This gives guest 1 infinitely many adjustments; 1 ends up at place 1 + sum(j > 1) delta_j = 1 + sum(j > 1) {2 [ 1/(2j-1) - 1/2j ] } = 2 ln(2).
show/hide this revision's text 1

I'll now put forward my candidate solution to the problem. It clearly satisfies the hurdle condition, but I can't prove its optimality. To get a handle on the algorithm, let's represent $x_1$ , $x_2$ , … as hotel guests numbered accordingly. Recall Hilbert's hotel, where the unfortunate guests were ever being shunted from their room to a higher-numbered room. The hotel in this case, rather than having a countably infinite number of discrete rooms, is a continuum of “rooms”, represented by the points of a closed bounded real interval; [0 , 1.4] is big enough, as it turns out). The “guests”, numbered 1, 2, … , are movable tags, each assigned to a rational point in the interval. Unlike Hotel Hilbert, which is always full, this hotel starts empty apart from the proprietor who resides permanently at 0, and the guests arrive one by one in the order 1, 2, … . The proprietor operates the strict rule that, when there are a total of $m$ guests in the hotel, there must be a space of at least $1/m$ between the residents (including himself), for $m$ = 1, 2, … . Guest 1 is assigned to the point 1. Guest 2 is placed at 1/2. When guest 3 arrives, she is put at 1/3, while guests1 and 2 are moved up by a distance 2/3 – 2/(3 + 1) = 1/6. When guest 4 comes, he is allotted to 1/2 + 1/6 + 1/4 = 11/12. The general rule is as follows. For $k$ = 1, 2, … , after $2k$ guests have been accommodated, the next $2k$ are put consecutively into the $2k$ spaces between the proprietor and the first $2k$ guests, in left-to-right order: An odd-numbered arrival, say guest $2n$ – $1$, is assigned to the point below her right-hand neighbour (guest $n$) that is 1/($2n$ – $1$) above her left-hand neighbour, while all the guests to her right are moved up by a distance 2/($2n$ – 1) – $1/n$; when the next, even-numbered, guest arrives (guest $2n$), he can just go to the midpoint of the next space up, at a distance 1/$2n$ above his left-hand neighbour (guest $n$), and mercifully no resident has to move until the next (odd-numbered) guest arrives. The result is that the guests, now identified with their limiting room positions, are each the sum of two parts: The first part is a sum of a finite number of distinct fractions of the form $1/n$, while the second is an infinite series whose terms are of the form 1/$n$($2n$ – 1), where $n$ is a positive integer. Generally an infinite number of terms of the latter type are absent; only in the case of $x_1$ is the series free of gaps, and then the first “sum” has only one term. Thus $x_1$ = 1 + ∑{1/$j$($2j$ – 1) : $j$ = 2, 3, …} = ln 4, and this is also the supremum of the sequence.

An alternative characterization, suggested by Gerhard Paseman, is as follows: For j from 2^(k-1)+1 to 2^k, you will arrange to place guest (2j-1) to the left of guest j and guest 2j to the right of guest j. Since space to the left of guest j has previously been guaranteed to be 1/j from his/her lefthand neighbor, guest (2j-1) needs more since it needs 1/(2j-1) space to his/her left and right. So add the difference delta_j = (2/(2j-1) – 1/j) to the left of guest j and shift guest j and every guest on the right of guest j by this difference delta_j. Since guest 2j does not need more than 1/j = (2/2j) space, no such adjustment is needed for guest 2j. This gives guest 1 infinitely many adjustments; 1 ends up at place 1 + sum(j > 1) delta_j = 1 + sum(j > 1) {2 [ 1/(2j-1) - 1/2j ] } = 2 ln(2).