IRL_ABooklet_2023

Let's generalise and consider exactly $n$ letters in a word, chosen from an alphabet of $m$ letters, with the restriction that any two distinct words must differ in at least two places. We claim that this allows for at most $m^{n-1}$ words, and that this bound can be obtained. Since $20^{7-1}=64000000$ lies strictly between $60$ and $70$ million, Leonard's colleague makes a valid point, but we need to prove our claim!

The upper bound follows easily from the pigeonhole principle since there are $m^{n-1}$ possibilities for the first $n-1$ letters in a word. Thus, if there are more than this number of words, at least two of them must have the same first $n-1$ letters and so cannot differ at two or more places.

Conversely, consider the set of near-words consisting of $n-1$ letters from the alphabet, but with no restriction on the number of differences between two near-words. Clearly, there are $m^{n-1}$ near-words. Treat the letters as base-$n$ digits and create a word $W$ from each near-word $w$ by appending a single letter $s(w)$ that is congruent to the sum of the letters in $w$ modulo $n$. This gives a collection of $m^{n-1}$ words with the right number of letters and the right alphabet. But do they all differ in at least two places?

Suppose the distinct near-words $x$ and $y$ give rise to words $X$ and $Y$, respectively, by this process. If $x$ and $y$ differ in at least two places, so do $X$ and $Y$. If $x$ and $y$ differ in only one place, then $s(x)$ and $s(y)$ are different, and so $X$ and $Y$ differ in exactly two places.