Detailed mathematical approach

Problem Summary

We seek the minimum possible value of \(x_1+\cdots+x_{17}\) for points added one at a time inside the unit interval. After the \(m\)-th insertion, the current set of \(m\) points must occupy the \(m\) half-open subintervals

$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$

exactly once. So the first stage uses one bin, the second stage must place two points into the two halves, the third stage must place three points into the thirds, and so on up to \(m=17\). The implementations compute the optimal sum exactly, prove that \(17\) stages are feasible, and also verify that the same condition fails at \(18\).

Mathematical Approach

The key simplification is to represent uncertainty by rational intervals instead of individual real numbers. Every future decision only cuts intervals by equal-partition boundaries, so the whole search can be done with integer arithmetic.

Step 1: Put Every Boundary on One Common Grid

Let

$d=\operatorname{lcm}(1,2,\dots,17).$

Because every \(m\le 17\) divides \(d\), every boundary \(k/m\) can be written exactly as an integer multiple of \(1/d\). Instead of storing a point \(x\), we store an interval

$I=[l,u)\subseteq[0,d),$

which means that the real point may lie anywhere in

$\left[\frac{l}{d},\frac{u}{d}\right).$

Initially nothing is known, so the first state is just one interval:

$[0,d).$

Step 2: Describe the Transition from \(n\) Points to \(n+1\) Points

Assume a state with \(n\) current intervals already encodes all constraints from stages \(1\) through \(n\). For the next stage set

$m=n+1.$

The unit interval is now partitioned into \(m\) equal bins, which on the common denominator grid become

$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$

Each existing interval \(I_i\) must be assigned to one distinct bin with nonempty intersection. If bin \(B_{\pi(i)}\) is chosen, the interval is refined to

$I_i'=I_i\cap B_{\pi(i)}.$

Exactly one bin is left unused, and that unused bin becomes the interval of the newly inserted point. If no injective assignment exists, that branch of the search is impossible.

Step 3: View Feasibility as a Matching Problem

For a fixed stage \(m\), form a bipartite graph whose left side is the current intervals and whose right side is the \(m\) bins. Connect \(I_i\) to \(B_k\) whenever

$I_i\cap B_k\ne\varnothing.$

A valid transition is exactly an injective matching of the \(n\) current intervals into the \(m\) bins, leaving one unmatched bin for the new point. This is the Hall-type combinatorial core of the problem. The implementations do not invoke a separate matching library; instead they search directly through these assignments and prune as soon as a state becomes impossible.

Step 4: Canonical States Remove Label Symmetry

Once only the set of surviving intervals matters, the names of the points no longer matter. After every transition, the intervals are sorted by their endpoints. Two different histories that produce the same sorted interval list therefore represent exactly the same future problem.

This turns the search into dynamic programming on canonical states. A state is fully described by its sorted half-open intervals, and every repeated state can reuse the previously computed result instead of exploring the whole subtree again.

Step 5: The Objective Is the Sum of Left Endpoints

When the search reaches \(17\) intervals, each interval \(I_i=[l_i,u_i)\) contains all admissible final positions of one point. Since the target quantity is the sum of coordinates and every interval includes its left endpoint, the minimum achievable sum inside that terminal state is

$\frac{1}{d}\sum_{i=1}^{17} l_i.$

Choosing any point farther to the right can only increase the total. So the global optimization problem reduces to minimizing the integer numerator

$F=\sum_{i=1}^{17} l_i,$

and converting to the real answer only once, at the end, by dividing by \(d\).

Worked Example: The \(4\)-Point Check

The implementations include a small exact checkpoint at target \(4\). Then

$d=\operatorname{lcm}(1,2,3,4)=12.$

One optimal chain of states is

$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$

At the fourth stage the quarter bins are \([0,3)\), \([3,6)\), \([6,9)\), and \([9,12)\). An optimal refinement is

$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$

The unused bin is \([3,6)\). Therefore the four final left endpoints are \(0,3,6,9\), so

$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$

This is exactly the verification embedded in the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They first build the common denominator \(d\), then represent every state as a sorted list of half-open intervals with integer endpoints. From a state with \(n\) intervals, the implementation creates the \(n+1\) equal bins for the next stage and computes every nonempty interval-bin intersection.

If some interval has no compatible bin, the state is rejected immediately. Otherwise the search tries injective assignments, always considering first the interval with the fewest available bins, because that ordering cuts the branching factor sharply. One memoized search answers the yes-or-no question “can this state still be completed?”, and another memoized search returns the minimum possible numerator \(F\) reachable from that state.

The final decimal output is produced by exact integer rounding of \(F/d\) to twelve digits after the decimal point. The implementations also perform three internal consistency checks: the \(4\)-point value is \(3/2\), the \(6\)-point dynamic program agrees with a brute-force search, and feasibility is true for \(17\) but false for \(18\).

Complexity Analysis

For a state containing \(n\) intervals, constructing the next-stage bins and all interval-bin intersections costs \(O(n^2)\), because there are \(n\) intervals and \(n+1\) bins. The difficult part is the search over injective assignments, whose worst-case size is combinatorial, so the theoretical upper bound is exponential in the target size.

In practice, three features make the problem tractable for \(17\): interval intersections shrink the options quickly, branching starts with the most constrained interval, and canonical-state memoization merges many different histories into the same subproblem. Therefore the real running time is governed by the number of distinct canonical interval states that are visited, while memory is proportional to the number of cached states times the interval data stored for each one.

Footnotes and References

1. Problem page: Project Euler 794 - Seventeen Points
2. Least common multiple: Wikipedia - Least common multiple
3. Hall's marriage theorem: Wikipedia - Hall's marriage theorem
4. Bipartite graph: Wikipedia - Bipartite graph
5. Dynamic programming: Wikipedia - Dynamic programming