Every binary number coincides in more than half of bits Let $n\in\mathbb{Z}^+$. We would like to pick some binary numbers of length $2n+2$ so that any binary number of length $2n+2$ coincides with one of the picked numbers in at least $n+2$ positions (that is, strictly more than half of the positions.) At least how many numbers do we have to pick?
We can pick all numbers whose number of $1$'s is $0$ or $2n+1$, hence $\binom{2n+2}{0}+\binom{2n+2}{2n+1}=2n+3$ numbers. Then a number whose number of $1$'s is between $0$ and $n$ is "similar to" $00\ldots 0$, while a number whose number of $1$'s is between $n+1$ and $2n+2$ is "similar to" some number with $2n+1$ $1$'s. 
Is this the minimum possible?

We need just 4 numbers. First, let's consider just two of those 4 numbers. One with all $2n+2$ bits 0 and one with all $2n+2$ bits 1. Any number of the length $2n+2$ will have either number of 1's or number of 0's greater than or equal to $n+1$. These two numbers will cover all the numbers with number of bits = $2n+2$ other than those which have exactly $n+1$ 0's and $n+1$ 1's. To cover these numbers too, let's use 2 more numbers : 100...00(1 followed by $2n+1$ 0's) and 011...11 (0 followed by $2n+1$ 1's). If the number has a 1 as the first bit, then 100...00 will cover that number else 011...11 will cover that number.
Edit : Refer Hagen's comment for the proof that we can't do better than 4 numbers.
