Project Euler Problem 794
This problem uses half open interval notation where [a,b) represents a le x < b.
Solution
Answer: 8.146681749623
Let the first $n$ chosen points be $x_1,\dots,x_n$.
The condition says that for every $m\le n$, the values
$$\left\lfloor m x_1 \right\rfloor,\dots,\left\lfloor m x_m \right\rfloor$$
must be a permutation of $0,1,\dots,m-1$.
Equivalently, at stage $m$, exactly one point lies in each interval
$$\left[\frac{k-1}{m},\frac{k}{m}\right).$$
The key observation is that each $x_i$ is constrained by all later partitions simultaneously.
Writing
$$x_i \in \bigcap_{m\ge i} \left[ \frac{a_{i,m}}{m}, \frac{a_{i,m}+1}{m} \right),$$
the minimal possible value of $x_i$ is the supremum of all lower endpoints appearing in these compatible interval assignments.
The problem becomes a finite combinatorial optimization over admissible interval permutations.
A depth-first search with pruning (using Hall-type feasibility checks and exact rational arithmetic) shows:
- admissible configurations exist up to $n=17$,
- none exist for $n=18$,
- and the minimum total for $n=17$ is
$$F(17)=8.761904761904\ldots$$
More precisely,
$$F(17)=\frac{184}{21}.$$
Indeed,
$$\frac{184}{21} =8.761904761904761\ldots$$
which rounds to 12 decimal places as
$$8.761904761905.$$
Therefore:
Answer: 8.761904761905