Problem 1368

Let $p$, $q$ be two binary sequences. Define $d(p, q)$ as the number of positions $p$ and $q$ differ.

Lemma. $d$ satisfies the triangle inequality, that is, $d(p, q) \le d(p, r) + d(r, q)$ for all binary sequences $p$, $q$, $r$.

Proof. $p$ and $r$ differ in $d(p, r)$ positions, so they coincide in $24 - d(p, r)$ positions. Of these positions, in at most $d(q, r)$ positions $q$ and $r$ differ, so $p$, $q$ and $r$ coincide in at least $24 - d(p, r) - d(q, r)$ positions. So $d(p, q) \le d(p, r) + d(r, q)$.

Define the sphere with center $p$ as the set of binary sequences $q$ such that $d(p, q) \le 4$. Let $S$ be a set of binary sequences of length $24$ so that any two differ in at least $8$ positions and $p_1$, $p_2$ two binary sequences from $S$. If the spheres with centers $p_1$ and $p_2$ have an intersection, then $p_1$ and $p_2$ are at distance at most $4 + 4 = 8$. So $d(p_1, p_2) = 8$ and for all sequences $q$ in the intersection $d(p_1, q) = d(p_2, q) = 4$. Each sequence $q$ belongs to at most $24 / 4 = 6$ spheres with center in $S$, because if $q$ belongs to more spheres then there are two sequences $q_1$ and $q_2$ such that they differ with $q$ in the same positions. This means that $d(q_1, q_2) < d(q_1, q) + d(q, q_2) = 8$, contradiction.

The number of sequences in each sphere is $\binom{24}{0} + \binom{24}{1} + \binom{24}{2} + \binom{24}{3} + \binom{24}{4}$. Since each pair of spheres can intersect and each sequence belongs to at most $6$ spheres,
$$|S| \cdot \left( \binom{24}{0} + \binom{24}{1} + \binom{24}{2} + \binom{24}{3} + \frac{1}{6} \binom{24}{4} \right) \le 2^{24} \\ \iff |S| \cdot 4096 \le 2^{24} \iff |S| \le 4096$$