SILK ROAD MATHEMATICS COMPETITION XVII

Answer: $n+1$ for $n\ne 2$ and $4$ for $n=2$. For $n\ne 2$, take all words consisting only of letters $a$ and $b$, in which each letter $a$ to the left of each letter $b$, and for $n=2$ the words $aa,ab,ba,bb$.

Let us prove that more words can not be chosen. Consider two selected words $A$ and $B$, located at the largest distance $m$. Suppose that the selected word $C$ is from $A$ at a distance $k>0$. Then $\rho (B,C)$ is equal to the sum or difference of $\rho (A,B)=m$ and $\rho (A,C)=k$ and does not exceed $m$, hence $\rho (B,C)=m-k$. Now, if some selected word $C^{\prime }\ne C$ is also from $A$ at distance $k$, we can assume without loss of generality $k\ge m/2$ (otherwise, we can swap $A$ and $B$). The distance between $C$ and $C^{\prime }$ can not be equal to $k-k=0$, therefore, it is equal to $k+k\ge m$, and hence $k=m/2$.

So, we have that for each $k$, $0\le k\le m$, except, perhaps, for $k=m/2$, among the selected words no more than one, located from $A$ at distance $k$. The selected words, which are at a distance of $m/2$ from $A$, are no more than 2 (we showed that the distance between any two such words is $m$, therefore none of the three words lies between the two others).

It remains to check that if $m>2$ and two words are chosen at a distance $k=m/2$ from $A$, then there are at most 4 words. Indeed, let $\rho (A,C)=\rho (A,C^{\prime })=k=m/2$, and we have chosen some other word $D$. As in the previous argument, we can assume without loss of generality that $\rho (A,D)=s<k$. Then $\rho (B,D)=2k-s$ and $\rho (D,C)=\rho (D,C^{\prime })=k-s$ (the distance between $D$ and $C$ can not be equal to the sum $\rho (B,D)+\rho (B,C)=2k-s+k>2k$, so it is equal to

the difference $\rho (B,D)-\rho (B,C)$). It turns out that among the three distances $k-s,k-s,2k$, the words $D,C,C^{\prime }$ are not equal to the sum of the other two, a contradiction. This proves the estimate: if $m>2$, then for each $k\le n$ there is at most one selected word at a distance of $k$ from $A$, and there are no more than $n+1$ words in total, and if $m=1$ or $2$, then there are no more than 4 words.