5. Let $S$ be a set of sequences of length 15 formed by using the letters $a$ and $b$ such that every pair of sequences in $S$ differ in at least 3 places. What is the maximum number of sequences in $S$ ?
Solution. The answer is $2^{11}=2048$.
We may identify $a$ as 0 and $b$ as 1 . Then $S$ is simply the set of binary 15tuples satisfying the condition that any two tuples in $S$ differ in at least 3 places. For each element $s$ of this set $S$, there are exactly $15+1=16$ tuples (including itself) that differ from it in at most 1 place. Let $B_{s}$ denote the set of these tuples. For any distinct $s, t \in S$, we must have $B_{s} \cap B_{t}=\emptyset$, otherwise $s$ and $t$ would differ in at most two places. Hence $|S| \cdot 16 \leq 2^{15}$, and so $|S| \leq 2^{11}$. An explicit $S$ meeting the upper bound is then given as follows:
For each of the $2^{11}$ tuples $\left(a_{1}, \ldots, a_{11}\right)$, associate to it the tuple $a=\left(a_{1}, \ldots, a_{15}\right)$ in $S$, where
$$
\begin{array}{l}
a_{12}=a_{5}+a_{6}+a_{7}+a_{8}+a_{9}+a_{10}+a_{11}(\bmod 2) \\
a_{13}=a_{2}+a_{3}+a_{4}+a_{8}+a_{9}+a_{10}+a_{11}(\bmod 2) \\
a_{14}=a_{1}+a_{3}+a_{4}+a_{6}+a_{7}+a_{10}+a_{11}(\bmod 2) \\
a_{15}=a_{1}+a_{2}+a_{4}+a_{5}+a_{7}+a_{9}+a_{11}(\bmod 2)
\end{array}
$$

To verify that this $S$ is indeed valid, simply check that if any one of the first eleven values of $a$ are changed, then at least two of $a_{12}, a_{13}, a_{14}, a_{15}$ must also be changed, and if any two of the first eleven values of $a$ are changed, then at least one of $a_{12}, a_{13}, a_{14}, a_{15}$ must also be changed.