
Problem 1. Let $n$ be a natural number. Find the least natural number $k$ for which there exist $k$ sequences of 0 's and 1's of length $2 n+2$ with the following property: any sequence of 0 's and 1 's of length $2 n+2$ coincides in at least $n+2$ positions with some of these $k$ sequences.


Solution: We shall prove that $k=4$. Assume that $k \leq 3$ and let the respective sequences be $a_{1}^{i}, a_{2}^{i}, \ldots, a_{2 n+2}^{i}$ for $i=1, \ldots, k$. Since $k \leq 3$ there is a sequence $b_{1}, b_{2}, \ldots, b_{2 n+2}$ such that $\left(b_{2 l+1}, b_{2 l+2}\right) \neq$ $\left(a_{2 l+1}^{i}, a_{2 l+2}^{i}\right)$ for $l=0,1 \ldots, n$ and $i=1, \ldots, k$. This is a contradiction. For $k=4$ it is easily seen that the sequences $000 \ldots 0,011 \ldots 1$, $100 \ldots 0,111 \ldots 1$ have the required property.
