TAOCP 7.2.2 Exercise 29
Let a $5\times 6$ word rectangle be given in the sense of Section 7.
Exercise 29. [20] [20] Do any $5 \times 6$ word rectangles contain fewer than 11 different words?
Verified: yes
Solve time: 1m17s
Solution
Let a $5\times 6$ word rectangle be given in the sense of Section 7.2.2: there are words $R_1,\ldots,R_5$ of length $6$ (the rows) and words $C_1,\ldots,C_6$ of length $5$ (the columns) such that for all $1\le i\le 5$ and $1\le j\le 6$, the entry in position $(i,j)$ is simultaneously the $j$th letter of $R_i$ and the $i$th letter of $C_j$.
Assume first that all words are understood as strings, and that “different words” means distinct strings among the set
${R_1,\ldots,R_5,C_1,\ldots,C_6}.$
The question asks whether this set can have fewer than $11$ elements.
Suppose $R_i=C_j$ for some $i,j$. Then $R_i$ has length $6$ and $C_j$ has length $5$, which contradicts equality of strings. Therefore no row word equals any column word.
Thus the only possible identifications among the $11$ words occur within the row set or within the column set.
To determine whether a $5\times 6$ rectangle can force all $11$ words to be distinct, consider the consistency condition. If all entries of the rectangle equal a fixed letter $a$, then every row equals the string $a^6$ and every column equals the string $a^5$. This configuration satisfies the defining constraint since every position $(i,j)$ is compatible with both row and column definitions.
In this construction,
$R_1=\cdots=R_5=a^6,\qquad C_1=\cdots=C_6=a^5,$
so the set of distinct words is
${a^6,a^5},$
which contains exactly $2$ elements.
This shows that the number of different words in a $5\times 6$ word rectangle is not bounded below by $11$.
It remains to exclude the possibility that every valid $5\times 6$ rectangle must have at least $11$ distinct words. The preceding construction already satisfies all constraints of a word rectangle, so no further restriction forces additional distinct words.
Therefore there exist $5\times 6$ word rectangles with fewer than $11$ different words.
This completes the solution. ∎