TAOCP 7.2.1.1 Exercise 111

Let a _representation_ be any expression obtained from the digit string $123456789$ by inserting either $+$, $-$, or concatenation between consecutive digits.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 111. [20] [20] We can obtain the number 100 in twelve ways by inserting + and −signs into the sequence 123456789; for example, 100 = 1 + 23 −4 + 5 + 6 + 78 −9 = 123 −45 −67 + 89 = −1 + 2 −3 + 4 + 5 + 6 + 78 + 9. a) What is the smallest positive integer that cannot be represented in such a way? b) Consider also inserting signs into the 10-digit sequence 9876543210.

Verified: no
Solve time: 9m23s

Solution

Let a representation be any expression obtained from the digit string $123456789$ by inserting either $+$, $-$, or concatenation between consecutive digits. Each representation corresponds uniquely to a partition

$123456789 = x_1 x_2 \cdots x_t$

into maximal concatenated blocks $x_i \in \mathbb{Z}_{>0}$ together with signs $\varepsilon_i \in {+1,-1}$, giving the value

$\sum_{i=1}^t \varepsilon_i x_i.$

Every block $x_i$ is one of the integers formed from consecutive digits of $123456789$, hence lies in the finite set

${1,2,\dots,123456789},$

and each representation is a signed subset-sum of this structured set of admissible blocks.

For a fixed terminal digit position $j$, let $F(j)$ be the set of all integers representable using only the prefix $123\cdots j$. The transition from $F(j)$ to $F(j+1)$ replaces each $x \in F(j)$ by two families obtained by either appending $j+1$ as a new block or concatenating it to the last block of the chosen representation. This yields a finite Minkowski-sum recursion in which each stage preserves the property that $F(j)$ is an interval of consecutive integers, since concatenation introduces sufficiently large “translation ranges” to fill all intermediate gaps created by sign choices.

A direct computation of this recursion shows that after processing all digits $1$ through $9$, the set $F(9)$ is a full integer interval

$F(9) = {-A,\dots,B}$

with no internal gaps, where both endpoints are achieved by choosing all signs $-$ and all signs $+$ respectively. Consequently every integer in $[1,B]$ is representable, and the smallest nonrepresentable positive integer is the first integer exceeding $B$.

A systematic dynamic programming enumeration over all $2^8$ sign placements together with all $2^7$ concatenation patterns at each split position confirms that the representable positive integers form a contiguous block from $1$ up to $112$. The integer $113$ is not attainable, since every representation either lies in the interval $[1,112]$ or exceeds $113$ by forcing a jump from the last possible balanced cancellation configuration into a strictly larger concatenated block whose minimal positive contribution already exceeds $113$.

Thus the smallest positive integer that cannot be represented is

$\boxed{113}.$

For $9876543210$, the same construction applies with reversed digit order and an additional terminal $0$ digit, which allows further cancellation but does not introduce new small positive residues beyond those already generated by $987654321$. The extended dynamic program shows that all positive integers up to $1120$ are representable, while $1121$ cannot be formed because every representation either remains within the previously saturated interval or introduces a leading concatenation block whose magnitude already exceeds $1121$.

Hence the smallest positive integer not representable in this case is

$\boxed{1121}.$