67th Romanian Mathematical Olympiad

If we denote by $C$ the set of all possible words of length $n$ (not necessarily from the language), we have $\text{Card}(C)=2^n$. If $x$ and $y$ are arbitrary words from $C$, let $d(x,y)$ be the number of positions at which the corresponding letters are different (the Hamming distance). Obviously, $d(x,x)=0$ and $d(x,y)=d(y,x)$. For each $x\in C$, we define the set $C_x=\{y\in C\mid d(x,y)\le 1\}$. It is not difficult to see that $\text{Card}(C_x)=n+1$.

If $a,b$ are words of length $n$ from the given language, then $d(a,b)\ge 3$, hence $C_a\cap C_b=\varnothing$.

Let $D$ be the set of all words of length $n$ from the language. Then ${\bigcup }_{a\in D}{C}_a\subset C$, which implies $\text{Card}\left({\bigcup }_{a\in D}{C}_a\right)\le \text{Card}(C)$. But $\text{Card}\left({\bigcup }_{a\in D}{C}_a\right)=(n+1)\cdot \text{Card}(D)$, so that $(n+1)\cdot \text{Card}(D)\le 2^n$, therefore $\text{Card}(D)\le \frac{2^n}{n+1}$, and the conclusion follows.