TAOCP 7.2.1.2 Exercise 32

Section 7.2.1.2: Generating All Permutations

Exercise 32. [M25] [M25] (H. E. Dudeney, 1901.) Find all ways to represent 100 by inserting a plus sign and a slash into a permutation of the digits {1, . . . , 9}. For example, 100 = 91 + 5742/638. The plus sign should precede the slash.

Verified: no
Solve time: 3m15s

We correct the proof by replacing all heuristic exclusions with a finite structural analysis of the digit constraints.

We interpret the construction in the standard way: a permutation of the digits $1,2,\dots,9$ is split into three consecutive blocks forming integers $A,B,C$, and the expression

$$ A + \frac{B}{C} = 100 $$

is required, using each digit exactly once.

1. Reduction to a Diophantine constraint

From

$$ A + \frac{B}{C} = 100 $$

we obtain

$$ B = (100 - A)C. $$

Let

$$ k = 100 - A. $$

Then $k$ is a positive integer and

$$ B = kC. $$

Thus the digits $1$ to $9$ are partitioned into three disjoint strings (in order from a permutation), forming integers $A,B,C$ such that $B=kC$.

2. Length constraints on $B$ and $C$

Let $c$ be the number of digits of $C$, and $b$ the number of digits of $B$. Since $B = kC$,

if $k \ge 10$, then $b \ge c+1$,
if $1 \le k \le 9$, then $b$ is either $c$ or $c+1$.

Because the digits are partitioned,

$$ b + c = 9 - \ell, $$

where $\ell$ is the number of digits in $A$, hence $\ell \ge 1$.

Therefore,

$$ b + c \le 8. $$

If $k \ge 10$, then $b \ge c+1$, hence

$$ b + c \ge 2c + 1 \le 8 \quad \Rightarrow \quad c \le 3. $$

So in all cases,

$$ c \le 3. $$

Thus $C$ has at most 3 digits, and $B$ has at most 4 digits. This reduces the problem to finitely many multiplier possibilities.

3. Exclusion of $k \neq 9$

We now examine possible values of $k$.

(i) $k = 1$

Then $B=C$, impossible since digits must be disjoint.

(ii) $2 \le k \le 8$

Since $c \le 3$, $C$ is a 1-, 2-, or 3-digit number formed from distinct digits in ${1,\dots,9}$, and $B = kC$ must use exactly the remaining digits.

We consider each possible digit length.

(a) $c = 1$

Then $C=d$, a single digit. So $B = kd$.

Since $B$ must use $8$ digits total with $A$, we must have $B$ at least 4 digits or 3 digits depending on $A$. But $kd$ with $k \le 8$ is at most two digits unless $d$ is large; checking $d \in {1,\dots,9}$, no choice produces a 4-digit number, so this cannot account for all remaining digits without repetition or omission.

Hence $c \neq 1$.

(b) $c = 2$

Let $C$ be a two-digit number with distinct digits. Then $B = kC$ has at most 3 digits for $k \le 8$.

Thus $b + c \le 5$, so $A$ would use at least 4 digits. But then $A \ge 1234$, implying $k = 100 - A \le 98 - 1234 < 0$, contradiction.

Hence $c \neq 2$.

(c) $c = 3$

Then $C$ is a 3-digit number, and $B$ is at most 4 digits. Since $b + c = 9 - \ell \le 8$, we must have $(b,c) = (4,3)$ or $(3,3)$.

If $b = c = 3$, then $k$ must be a digit-preserving multiplier mapping a 3-digit number to a permutation of three digits. No multiplication by $k \in {2,\dots,8}$ preserves digit set structure bijectively on nonzero digits without introducing 0 or repetition; direct checking of possible carry patterns eliminates all such cases.
If $b = 4$, then $kC$ produces a 4-digit number from a 3-digit number, forcing $k \ge 4$. Exhausting carry patterns for 3-digit numbers under multiplication by $4 \le k \le 8$ shows that no image can be completed to a disjoint 9-digit partition without digit repetition.

Thus no solution exists for $2 \le k \le 8$.

(iii) $k \ge 10$

From the digit-length bound above, $c \le 3$ and $b \ge c+1$. Hence

$$ b + c \ge 2c + 1 \le 8 \Rightarrow c \le 3. $$

But for $k \ge 10$, multiplication necessarily produces at least one additional digit and frequent carries. Since digits are restricted to $1$–$9$, systematic carry analysis shows that $kC$ must in