Seventeen Points

This problem uses half open interval notation where $[a,b)$ represents $a \le x < b$. A real number, $x_1$, is chosen in the interval $[0,1)$. A second real number, $x_2$, is chosen such that each of $[0,\frac{1}{2})$ and $[\frac{1}{2},1)$ contains exactly one of $(x_1, x_2)$. Continue such that on the $n$-th step a real number, $x_n$, is chosen so that each of the intervals $[\frac{k-1}{n}, \frac{k}{n})$ for $k \in \{1, ..., n\}$ contains exactly one of $(x_1, x_2, ..., x_n)$. Define $F(n)$ to be the minimal value of the sum $x_1 + x_2 + ... + x_n$ of a tuple $(x_1, x_2, ..., x_n)$ chosen by such a procedure. For example, $F(4) = 1.5$ obtained with $(x_1, x_2, x_3, x_4) = (0, 0.75, 0.5, 0.25)$. Surprisingly, no more than $17$ points can be chosen by this procedure. Find $F(17)$ and give your answer rounded to 12 decimal places.

This is actually a very complex problem. We’ll start by understanding the pattern that emerges as n increases. When selecting $x_n$, the optimal choice will always be in the interval $[\frac{n-1}{n},1)$. This is because for each subsequent step $n+1, n+2, …$, the $x_n$ you chose will never cause the new points to be shifted into a higher interval – it’s at the highest possible interval. At the same time, you maximize the chances that the new points fall into a lower interval, since you’re as far towards the right end of the interval spectrum as possible.

Given this, with each new step $n$, the new point added to the tuple will be $x_n = \frac{n-1}{n}$. However, each of these new points pushes a number of existing points leftwards into lower intervals. To calculate the minimal value of the sum $x_1 + x_2 + … + x_n$ at each step $n$, we need to account for the sum of the points that have been pushed left, as well as the addition of the new point.

By observing the changes as we add more points into the tuple, the numbers being moved with the addition of $x_n$ are $\frac{i-1}{i}$ for $i

More Answers: