We form all $n$-length words from a $k$-element ABC, which consist of all different letters. We connect two such words with an edge if they differ in exactly one position. What is the diameter of the graph thus obtained?
Solution. The problem only makes sense for $n \leq k$. If $n=k$, then any two words differ in at least two positions, so there is no edge in the graph; in this case, the diameter of the graph is infinite. Let us assume from now on that $n<k$.

We will show that the diameter of the graph (apart from the uninteresting case $n=1$) is $\left[\frac{3 n}{2}\right]$. First, consider the case when $n$ is even. Take any word $A_{1} A_{2} A_{3} \ldots A_{n}$. Let us examine how far this is from the word $A_{2} A_{1} A_{4} A_{3} \ldots A_{n} A_{n-1}$. Let's see how many edges we need to traverse to change $A_{1} A_{2}$ to $A_{2} A_{1}$. Let's call a step the act of traversing an edge. Since the words are made of different letters, there must be a step where $A_{1}$ or $A_{2}$ changes to a letter different from $A_{1}$ and $A_{2}$. Two more steps are needed for $A_{2}$ to appear in the first position and for $A_{1}$ to appear in the second position. Therefore, at least three steps are required. The changes at different positions do not affect each other, so at least $\frac{n}{2} \cdot 3$ steps are needed to change $A_{1} A_{2} A_{3} \ldots A_{n}$ to $A_{2} A_{1} A_{4} A_{3} \ldots A_{n} A_{n-1}$.

If $n$ is odd, then the distance between the words $A_{1} A_{2} A_{3} \ldots A_{n}$ and $A_{2} A_{1} A_{4} A_{3} \ldots A_{n-1} A_{n-2} A_{n+1}$ (where $A_{n+1} \neq A_{1}, A_{2}, A_{3}, \ldots, A_{n}$) is, similarly to the previous case,

$$
3 \cdot \frac{n-1}{2}+1=\left[\frac{3 n}{2}\right]
$$

since the $\frac{n-1}{2}$ pairs of elements can each be changed in three steps, and the single element can clearly be changed in one step.

So far, we have shown that there are points in the graph that are $\left[\frac{3 n}{2}\right]$ apart. We still need to show that every vertex can be reached from any other vertex in at most $\frac{n}{2} \cdot 3$ steps. For this, consider two arbitrary vertices, $A=$ $A_{1} A_{2} A_{3} \ldots A_{n}$ and $B=B_{1} B_{2} B_{3} \ldots B_{n}$. Then we can get from $A$ to $B$ by repeatedly applying the following steps: Step to a vertex where one of the letters in $A$ changes to the corresponding letter in $B$ - let's call such a step productive. We can only not take a productive step if we are at a vertex that is made of the same letters as $B$, but in a different order; in this case, the distance from $B$ is at least 2. In this case, let's step so that one of the letters $A_{i}$, which is in a different position from the one it occupies in $B$, is replaced by a letter $V$ that does not occur in $B$. This does not spoil the letters that have already been changed to the correct ones; let's call such a step unproductive. The next step can then place $A_{i}$ in its (correct) position in $B$. Since the (non-occurring in $B$) $V$ remains in the word, we can be sure to place one more letter in its correct position. This ensures that every unproductive step will be followed by (at least) two productive ones. Since the number of productive steps is $n$, the number of unproductive ones can be at most $\frac{n}{2}$, so in total, at most $n+\frac{n}{2}=\frac{3 n}{2}$ steps are sufficient.