The Fractions Puzzle

Nine different non-zero digits go in the nine boxes of $$\frac{A}{BC} + \frac{D}{EF} + \frac{G}{HI} \;=\; 1,$$ where $BC$ is shorthand for the two-digit number $10B + C$, and $EF$ and $HI$ likewise. Each of the digits $1$ through $9$ is used once. There is, up to the order of the three fractions, a single solution, $$\frac{9}{12} + \frac{5}{34} + \frac{7}{68} \;=\; 1,$$ and the eye can confirm it: $9/12$ is three-quarters, and $5/34 + 7/68 = 10/68 + 7/68 = 17/68$, the remaining quarter. This is problem forty-one of the CSPLib, the standard library of constraint benchmarks, and it generalises in a way that turns a one-line riddle into a question still partly open.

From three fractions to $n$

Replace three fractions by $n$ and ask for $3n$ non-zero digits with $$\sum_{i=1}^{n} \frac{x_i}{10 y_i + z_i} \;=\; 1.$$ Each digit from $1$ to $9$ may now be reused, between once and $\lceil n/3 \rceil$ times, so that the stock of nine digits keeps pace with the $3n$ boxes. At $n = 3$ the ceiling is one, every digit appears exactly once, and this is the original puzzle. Because each fraction is at least $1/99$, no more than $99$ of them can sum to $1$, so the family is finite. The question is the largest $n$ for which the digits can be found.

What makes it hard is not the combinatorics but the arithmetic. The obvious program reads the equation as written and adds the fractions in floating-point, and from about $n = 6$ rounding error starts to certify sums that are not really $1$. The obvious repair, clearing denominators by multiplying through by the product $\prod_i (10 y_i + z_i)$, replaces rounding error with overflow: that product passes a $32$-bit integer at $n = 6$ and a $64$-bit one not long after. The puzzle is a small monument to the gap between a model that is correct on paper and one that is correct in a machine.

Clearing the denominators

The cure is to clear the denominators with their least common multiple rather than their product. The two agree only when the denominators are coprime; in every solution they share factors heavily, and the least common multiple stays small where the product explodes. The whole model is built around one extra variable that carries it.

Variables

For each fraction $i \in \{1, \ldots, n\}$ three digit variables give its numerator and the two figures of its denominator, $$x_i,\, y_i,\, z_i \in \{1, \ldots, 9\}, \qquad d_i = 10 y_i + z_i \in \{11, \ldots, 99\}.$$

One linear equation

The constraint $\sum_i x_i / d_i = 1$ divides by unknown denominators, which no integer solver will accept. Clear them all at once. Let $L$ be a positive integer that every $d_i$ divides, and let $q_i = L / d_i$ be the corresponding cofactor. Then $x_i / d_i = x_i q_i / L$, and the sum-to-one condition becomes a single linear equation, $$\sum_{i=1}^{n} x_i q_i \;=\; L .$$ The cofactors and the divisibility are pinned by one family of product relations, $$L = d_i\, q_i \qquad (i = 1, \ldots, n),$$ which simultaneously force each $d_i$ to divide $L$ and define $q_i = L / d_i$. Any common multiple $L$ would serve, since the equation is unchanged by scaling $L$ and every $q_i$ together; minimising $L$ picks out the least common multiple, the smallest honest common denominator, and keeps the numbers as small as the puzzle allows. CP-SAT carries the handful of products $L = d_i q_i$ and $p_i = x_i q_i$ directly, which is all the model needs beyond linear constraints.

Counting and symmetry

Two families of constraints remain. The counting rule asks that each digit value $v$ be taken by between one and $\lceil n/3 \rceil$ of the $3n$ digit variables. And the $n$ fractions may be permuted freely, a symmetry that multiplies every solution by $n!$ copies; ordering the fractions by value removes it. Since $x_i / d_i = x_i q_i / L = p_i / L$ with a common $L$, ordering by value is just $p_1 \le p_2 \le \cdots \le p_n$ on the scaled numerators the model already has.

A solver

from ortools.sat.python import cp_model
from math import ceil

def n_fractions(n, lmax=200_000):
    m = cp_model.CpModel()
    x = [m.NewIntVar(1, 9, "") for _ in range(n)]  # numerators
    y = [m.NewIntVar(1, 9, "") for _ in range(n)]  # denom. tens
    z = [m.NewIntVar(1, 9, "") for _ in range(n)]  # denom. ones
    d = [m.NewIntVar(11, 99, "") for _ in range(n)]
    q = [m.NewIntVar(1, lmax, "") for _ in range(n)]
    p = [m.NewIntVar(1, lmax, "") for _ in range(n)]
    L = m.NewIntVar(1, lmax, "")
    for i in range(n):
        m.Add(d[i] == 10 * y[i] + z[i])
        m.AddMultiplicationEquality(L, d[i], q[i])
        m.AddMultiplicationEquality(p[i], x[i], q[i])
    m.Add(sum(p) == L)             # the sum equals 1
    for v in range(1, 10):         # digit v: 1..ceil(n/3)
        used = [m.NewBoolVar("") for _ in range(3 * n)]
        for b, g in zip(used, x + y + z):
            m.Add(g == v).OnlyEnforceIf(b)
            m.Add(g != v).OnlyEnforceIf(b.Not())
        m.AddLinearConstraint(sum(used), 1, ceil(n / 3))
    for i in range(n - 1):
        m.Add(p[i] <= p[i + 1])    # order fractions (symmetry)
    m.Minimize(L)                  # least common denominator
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    val = s.Value
    return [(val(x[i]), val(y[i]), val(z[i])) for i in range(n)]

For $n = 3$ the model returns the three fractions $9/12$, $5/34$, $7/68$ and nothing else: with the ceiling equal to one the counting rule forces all nine digits distinct, the symmetry order fixes their arrangement, and the common denominator comes out at $L = 204 = \operatorname{lcm}(12, 34, 68)$, against which $9 \cdot 17 + 5 \cdot 6 + 7 \cdot 1 = 204$ confirms the sum. The same code runs on without change. It finds twelve fractions inside a common denominator of only $78$, a vivid measure of how far the least common multiple lags the product, which by then would have hundreds of digits. Past the middle teens the search rather than the size is what slows, and reaching the frontier needs the sharper machinery below.

Where it stops

Two results bracket the answer. From above, the puzzle is impossible once $n$ is large enough, and the reason is a counting bound. To make the sum as small as it can be, put the smallest digits on top and the largest underneath, with each denominator’s tens figure no less than its ones figure (a larger denominator where it costs nothing). Even this most favourable arrangement has a sum that grows with $n$, and once it passes $1$ the equation cannot hold. Writing $n = 3k + r$, the minimal sum is at least $$\Bigl(\tfrac{1}{76} + \tfrac{2}{86} + \tfrac{3}{96}\Bigr) k \quad (r = 0), \qquad \Bigl(\tfrac{1}{77} + \tfrac{2}{87} + \tfrac{3}{97}\Bigr) k + \cdots \quad (r = 1, 2),$$ and these cross $1$ at $n = 45$, $46$, and $47$ respectively, so the bound clears $1$ for every $n \ge 45$. The fractions puzzle therefore has no solution from $n = 45$ on.

From below, a constraint search closes almost everything beneath that ceiling. Solutions exist for every $n$ from $3$ to $35$ and for $37$, $38$, and $40$; the largest fractions puzzle anyone has solved is the $40$-fraction one. Six cases, $n \in \{36, 39, 41, 42, 43, 44\}$, were neither solved nor ruled out and remain open, the multiples of three among them resisting longest because their tighter counting rule, every digit used exactly $k$ times, leaves the least room to manoeuvre. The gap between the largest solved puzzle and the proven ceiling is those six numbers, and closing it, finding a fraction or proving there is none, is the puzzle’s standing open problem.

Sources. The fractions puzzle is problem $041$ of the CSPLib, the constraint-satisfaction benchmark library, contributed by Alan Frisch, Christopher Jefferson, Ian Miguel, and Toby Walsh in $1999$; its $n$-fraction generalisation, the counting rule, and the symmetry-breaking orders trace through Christian Schulte and Gert Smolka and through Alan Frisch and collaborators’ studies of implied constraints. The least-common- multiple model used here, the proof that the puzzle is unsatisfiable for $n \ge 45$, and the search that solves it up to $40$ fractions while leaving $n \in \{36, 39, 41, 42, 43, 44\}$ open are due to Arnaud Malapert and Julien Provillard, Puzzle—Solving the $n$-Fractions Puzzle as a Constraint Programming Problem, INFORMS Transactions on Education volume $19$, number $1$ ($2018$), pages $48$–$55$, whose models reach the same frontier with a precomputed prime factorisation of each denominator in place of the bounded common multiple taken here. The unique three-fraction solution and the twelve-fraction instance are produced by the model above and re-checked in exact rational arithmetic.