TAOCP 7.2.2.1 Exercise 28

Formula (27) expresses the estimated completion ratio in the form $\prod_{j=0}^{t} \frac{c_j}{t_j}$ with integers satisfying $1 \le c_j \le t_j$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.1: Dancing Links

Exercise 28. [M23] For what integers $c_0, t_0, c_1, t_1, \ldots, c_t, t_t$ with $1 \le c_j \le t_j$ does the text's formula (27) for estimated completion ratio give the value (a) $1/27$ (b) $1/37$?

Verified: no
Solve time: 1m31s

Solution

Formula (27) expresses the estimated completion ratio in the form

$\prod_{j=0}^{t} \frac{c_j}{t_j}$

with integers satisfying $1 \le c_j \le t_j$.

The requirement

$\prod_{j=0}^{t} \frac{c_j}{t_j} = \frac{1}{27}$

implies

$\frac{\prod_{j=0}^{t} c_j}{\prod_{j=0}^{t} t_j} = \frac{1}{27}.$

Both products are positive integers. Hence

$\prod_{j=0}^{t} c_j = 1.$

Each factor satisfies $c_j \ge 1$, so every term must satisfy $c_j = 1$.

Substitution gives

$\frac{1}{\prod_{j=0}^{t} t_j} = \frac{1}{27},$

so

$\prod_{j=0}^{t} t_j = 27.$

Thus the data for the value $1/27$ consists exactly of all finite sequences of integers $t_0, t_1, \ldots, t_t$ with each $t_j \ge 1$ whose product equals $27$, together with $c_j = 1$ for every $j$.

The same reasoning applied to

$\prod_{j=0}^{t} \frac{c_j}{t_j} = \frac{1}{37}$

gives $\prod c_j = 1$, hence $c_j = 1$ for all $j$, and

$\prod_{j=0}^{t} t_j = 37.$

Since $37$ is prime, the only factorizations into positive integers are $37$ itself and $1 \cdot 37$ and $37 \cdot 1$ and, more generally, any insertion of additional factors equal to $1$.

Therefore the complete set of solutions is given by sequences with $c_j = 1$ for all $j$, and arbitrary integer sequences $(t_j)$ whose product is $27$ in case (a) and $37$ in case (b).

This completes the proof. ∎