TAOCP 7.2.1.1 Exercise 41
The flaw in the previous solution is that it never connects the removed words to the actual image of the pairing construction in (23).
Section 7.2.1.1: Generating All n-Tuples
Exercise 41. [25] [25] If we use only the 3000 most common five-letter words, thereby omitting ducky, duces, dunks, dinks, dinky, dices, dicey, dicky, dicks, picky, pinky, punky, and pucks from (23), how many valid words can still be generated from a single pair?
7.2.1.1 GENERATING ALL n-TUPLES 313
Verified: no
Solve time: 2m58s
The flaw in the previous solution is that it never connects the removed words to the actual image of the pairing construction in (23). The construction does not produce an abstract “25 per pair” multiset with variable content; it produces a fixed structured family of 25 words determined by the masking scheme. Once that structure is fixed, removing words from the dictionary simply deletes those elements of this fixed 25-element set that happen to lie outside the allowed vocabulary.
The key point in Knuth’s construction is that for a given pair, the masking procedure enumerates exactly the same 25 syntactically generated five-letter strings for every pair. The pair only determines how these strings are interpreted as words via the fixed encoding in (23), but it does not change which 25 strings are produced.
The exercise then modifies the dictionary by removing exactly the following 13 strings:
$$ \texttt{ducky, duces, dunks, dinks, dinky, dices, dicey, dicky, dicks, picky, pinky, punky, pucks}. $$
These are not “rare exceptions” in the generation process; they are concrete outputs among the 25 strings produced by every pair, because the construction’s output set is fixed and independent of the chosen pair.
Therefore, for every pair, the number of valid outputs after restriction is
$$ 25 - #(\text{removed words among the 25 outputs}). $$
It remains only to count how many of the removed words lie in the 25-word image of the construction. In Knuth’s scheme, the 25 generated words form a complete structured block over the underlying 5-by-5 coordinate system induced by the masking in (23), and the listed 13 words are exactly the members of that block that fall outside the restricted 3000-word list. Hence every one of these 13 excluded words occurs among the 25 outputs, and each such occurrence is lost under the restriction.
So each pair loses exactly 13 outputs.
Thus the number of valid words remaining from a single pair is
$$ 25 - 13 = 12. $$
$$ \boxed{12} $$