TAOCP 7.2.1.2 Exercise 23

Section 7.2.1.2: Generating All Permutations

Exercise 23. [M20] [M20] True or false: A pure alphametic cannot have two identical signatures sj = sk ̸= 0 when j ̸= k.

Verified: no
Solve time: 4m17s

The previous solution failed because it implicitly treated an “alphametic identity” as a manipulable symbolic cancellation pattern, rather than a polynomial identity that must hold for all digit assignments. Once that distinction is enforced, the structure of signatures becomes rigid.

A pure alphametic identity is an equation that is valid for every assignment of digits to letters in base $b$. After expanding each positional numeral into powers of $b$, the expression becomes a polynomial in the letter-variables with integer coefficients determined solely by column structure. Writing the identity in the standard TAOCP form, we obtain a decomposition by columns

$$ \sum_{k} b^{k} \left(\sum_{j} s_j(k),x_j \right) = 0 $$

which must hold for all digit assignments $(x_j)$.

Since the powers $b^k$ are linearly independent as functions of the base, each column polynomial must vanish identically. Therefore, for every column $k$,

$$ \sum_j s_j(k),x_j = 0 \quad \text{for all digit assignments.} $$

But the variables $x_j$ are independent indeterminates in the identity interpretation. The only way a linear form in independent variables can vanish identically is for all its coefficients to be zero. Hence for every letter $j$ and every column $k$,

$$ s_j(k) = 0. $$

So every signature vector is the zero vector:

$$ s_j = 0 \quad \text{for all } j. $$

This immediately resolves the question. Since no letter in a pure alphametic identity can have a nonzero signature at all, it is impossible for two distinct letters to share a nonzero signature.

In particular, the condition $s_j = s_k \neq 0$ can never occur.

Therefore the statement is true.