Problem 12.3. Find the maximal cardinality of a set of phone numbers satisfying the following three conditions:

a) all of them are five-digit numbers (the first digit can be 0 );

b) each phone number contains at most two different digits;

c) the deletion of an arbitrary digit in two arbitrary phone numbers (possibly in different positions) does not lead to identical sequences of digits of length 4 .

Ivan Landjev
12.3. Let $C$ be a set of phone numbers satisfying the given three conditions. Assume that $C$ has maximal cardinality. Denote by $A$ the set of phone numbers in $C$ which have four or five equal digits, and by $B$ the set of phone numbers in $C$ which have exactly three equal digits. Obviously, $C=A \cup B$. Also $|A| \leq 10$, since any digit can appear four or five times in at most one number in $C$.

Denote by $B_{i, j}, 0 \leq i, j \leq 9, i \neq j$, the set of phone numbers containing three digits $i$ and two digits $j$. We shall prove that the maximal cardinality of $B_{i, j} \cup B_{j, i}$ is 4 . It is enough to consider the case $i=0, j=1$. Let $a_{i}$ be the number of phone numbers in $B_{1}=B_{0,1} \cup B_{1,0}$ with $i$ blocks (a sequence $a_{k}, \ldots, a_{j}$ is called a block if $a_{k-1} \neq a_{k}=\cdots=a_{j} \neq a_{j+1}$.)

Assume that $\left|B_{1}\right|=5$. Then

$$
\begin{aligned}
a_{2}+a_{3}+a_{4}+a_{5} & =5 \\
2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5} & \leq 14
\end{aligned}
$$

since any two phone numbers have no common subsequence of length four. Moreover, it is easy to see that $a_{2} \leq 2$ и $a_{3} \leq 2$. Hence $a_{2}=a_{3}=2, a_{4}=1$. Then $01110,10001 \in B_{1}$ and it follows that $B_{1}$ does not contain a phone number with two blocks.

On the other hand, it is possible to find four phone numbers in $B_{1}$ which satisfy c). Take, for example, $B_{1}=\{10001,01010,11100,00111\}$.

The set $C$ can be written as

$$
C=A \cup B=A \cup\left(\cup_{0 \leq i<j \leq 9} B_{i, j} \cup B_{j, i}\right) .
$$

It is clear that for $(i, j) \neq(k, l)$ the choices of phone numbers in $B_{i, j} \cup B_{j, i}$ and $B_{k, l} \cup B_{l, k}$ are independent. Moreover, we may choose ten phone numbers in $A$ which are not in conflict with any choice of the other numbers in $C$. Take, for example, $A=\{00000,11111, \ldots, 99999\}$.

Thus the maximal cardinality of $C$ equals

$$
|C|=|A|+\sum_{0 \leq i<j \leq 9}\left|B_{i, j} \cup B_{j, i}\right|=10+\binom{10}{2} \cdot 4=10+45 \cdot 4=190
$$