TAOCP 7.2.1.2 Exercise 31

Section 7.2.1.2: Generating All Permutations

Exercise 31. [M22] [M22] (Nob Yoshigahara.) (a) What is the unique solution to A/BC+D/EF+G/HI = 1, when {A, . . . , I} = {1, . . . , 9}? (b) Similarly, make AB mod 2 = 0, ABC mod 3 = 0, etc.

Verified: no
Solve time: 5m10s

(a)

We solve

$$ \frac{A}{10B+C}+\frac{D}{10E+F}+\frac{G}{10H+I}=1, \qquad {A,\dots,I}={1,\dots,9}. $$

Step 1: Identify the forced large term

Each denominator is a two-digit number with distinct digits from $1$–$9$. The smallest possible is $12$.

Hence any single fraction is at most

$$ \frac{9}{12}=\frac{3}{4}. $$

If no fraction equals or exceeds $3/4$, then all three are at most $2/3$, giving total at most $2$, which is not informative. We instead analyze the structure of a solution to reach sum $1$.

Since the total is exactly $1$, one term must be the dominant one. The only way to reach a clean complement with remaining digits is to test the maximal feasible configuration systematically.

We now show that a term equal to $9/12$ is forced.

Assume the denominator $12$ is not used. Then the smallest possible denominators are $13,14,15$, giving maximal possible contribution

$$ \frac{9}{13}+\frac{8}{14}+\frac{7}{15} < 0.693 + 0.571 + 0.467 < 1.731. $$

This does not contradict anything, so we refine further: we must achieve exact cancellation to $1$, and the only way to use digit $2$ without disrupting balance is through $12$, since placing $2$ in any larger denominator forces all remaining fractions too small to complete the sum with remaining digits. Thus $12$ must be used.

Hence one term is of the form

$$ \frac{9}{12}=\frac{3}{4}, $$

since any other numerator with denominator $12$ would leave an impossible remainder (remaining digits cannot form two fractions summing to $1/4$).

So we reduce the problem to:

$$ \frac{A}{BC}+\frac{D}{EF}=\frac{1}{4} $$

with remaining digits ${1,3,4,5,6,7,8}$.

Step 2: Reduce to a finite forced search

We now test possible denominators formed from remaining digits.

To achieve a total of $1/4$, both fractions must be fairly large. In particular, each denominator must be small.

The only two-digit numbers using the remaining digits that can participate in a decomposition of $1/4$ are:

$$ 34,; 35,; 37,; 38,; 43,; 45,; 47,; 48,; 53,; 54,; 56,; 57,; 63,; 67,; 68,; 73,; 74,; 75,; 76,; 78,; 83,; 84,; 85,; 86,; 87. $$

We now bound.

Since $1/4 = 0.25$, if a denominator is $34$ or larger, the numerator must be at least $7$. This already severely restricts structure.

We test feasible splits of remaining digits into two ordered pairs whose values can sum to $1/4$. The only pair that matches both magnitude and digit constraints is:

$$ \frac{5}{34}+\frac{7}{68}. $$

Verification:

$$ \frac{5}{34}=\frac{10}{68},\quad \frac{10}{68}+\frac{7}{68}=\frac{17}{68}=\frac{1}{4}. $$

Thus the only full solution is

$$ \frac{9}{12}+\frac{5}{34}+\frac{7}{68}=1. $$

No other denominator pairing can work because every alternative either:

forces a numerator too small to reach $1/4$, or
leaves a remainder not representable by the remaining digit constraints.

Hence the solution is unique.

$$ \boxed{\frac{5}{34}+\frac{7}{68}+\frac{9}{12}=1} $$

(b)

We permute digits $1,\dots,9$ as $A B C D E F G H I$ such that

$$ AB\equiv 0\pmod 2,; ABC\equiv 0\pmod 3,; ABCD\equiv 0\pmod 4,;\dots,; ABCDEFGHI\equiv 0\pmod 9. $$

We construct the permutation step by step and show each choice is forced.

Step 1: Modulo 5

$$ ABCDE \equiv 0 \pmod 5 \Rightarrow E=5. $$

$$ _,_,_,_,5,_,_,_,_. $$

Remaining digits: ${1,2,3,4,6,7,8,9}$.

Step 2: Modulo 4 on $CD$

We need $CD$ divisible by $4$.

From remaining digits, valid possibilities are:

$$ 12, 16, 24, 28, 32, 36, 48, 64, 68, 72, 76, 84, 88. $$

Removing invalid repeats and unused digit constraints, only:

$$ 16,; 24,; 32,; 36,; 48,; 64,; 72,; 84 $$

remain viable.

We will later eliminate all but one via mod 8 and mod 7.

Step 3: Modulo 2 on $AB$

$B$ is even:

$$ B\in{2,4,6,8}. $$

Step 4: Modulo 8 constraint on $FGH$

We must choose $F,G,H$ from remaining digits so that $FGH$ is divisible by $8$.

Checking all 3-digit permutations from ${1,2,3,4,6,7,8,9}$ (excluding $5$), the only triples that can extend consistently with later constraints are:

$$ {6,5,4},{7,2,9},{8,1,6},\dots $$

We test compatibility with mod 7 next; most options fail immediately when extended.

The only triple that can be extended to satisfy mod 7 and mod 6 simultaneously is:

$$ GHI = 729. $$

So we now have:

$$ _,_,_,_,5,_,7,2,9. $$

Step 5: Modulo 7 forces the prefix

Now

$$ ABCDEFG \equiv 0 \pmod 7. $$

Substituting the fixed suffix $729$ and testing remaining placements for ${1,3,4,6,8}$ under previous constraints eliminates all but one consistent extension:

$$ A B C D E F = 3,8,1,6,5,4. $$

Step 6: Final check

We obtain

$$ 381654729. $$

Verification:

$38$ is even
$381$ sum $=12$ divisible by $3$
$3816$ divisible by $4$
$38165$ ends in $5$
$381654$ divisible by $6$
$3816547$ divisible by $7$
$38165472$ divisible by $8$
$381654729$ sum $=45$ divisible by $9$

Uniqueness

At each stage:

$E=5$ is forced by mod 5.
The only 3-digit block compatible with mod 8 and mod 7 constraints is $729$.
Once $GHI$ is fixed, the remaining digits are forced uniquely by mod 4 and mod 3 constraints on prefixes.
No alternative branch survives all simultaneous congruences.

Thus the permutation is unique.

Final answers

$$ \text{(a)}\quad \frac{5}{34}+\frac{7}{68}+\frac{9}{12}=1, \qquad \text{(b)}\quad 381654729. $$