I wonder why the problem used these numbers, and not sequences of length $2n$, with the condition of coincidence on $n+1$ positions (for positive integers $n\geq 1$). One reason would be that "natural" also includes $0$, but then it could have been stated as I say, with "natural" replaced by "positive integer". Another reason could be in order to "hide" the case $n=0$, when it is obvious we need all $k=4$ binary sequences of length $2$. Anyways, $k=4$ such sequences are enough, for example (under my notations) $\underbrace{00\ldots 00}_{2n}$, $\underbrace{11\ldots 11}_{2n}$, $\underbrace{00\ldots 0}_{2n-1}1$, $\underbrace{11\ldots 1}_{2n-1}0$. It remains to show that $k=3$ are not enough. WLOG those $3$ sequences are $\underbrace{0\ldots 0}_{d}\underbrace{0\ldots 0}_{x}\underbrace{0\ldots 0}_{y}\underbrace{0\ldots 0}_{z}$, $\underbrace{0\ldots 0}_{d}\underbrace{0\ldots 0}_{x}\underbrace{1\ldots 1}_{y}\underbrace{1\ldots 1}_{z}$ and $\underbrace{0\ldots 0}_{d}\underbrace{1\ldots 1}_{x}\underbrace{0\ldots 0}_{y}\underbrace{1\ldots 1}_{z}$, with $d+x+y+z=2n$. If $x,y,z$ are all even, take $S = \underbrace{1\ldots 1}_{d}\underbrace{0\ldots 0}_{x/2}\underbrace{1\ldots 1}_{x/2}\underbrace{0\ldots 0}_{y/2}\underbrace{1\ldots 1}_{y/2}\underbrace{0\ldots 0}_{z/2}\underbrace{1\ldots 1}_{z/2}$. If only one of $x,y,z$ is even, say $x$, take $S = \underbrace{1\ldots 1}_{d}\underbrace{0\ldots 0}_{x/2}\underbrace{1\ldots 1}_{x/2}\underbrace{0\ldots 0}_{(y-1)/2}\underbrace{1\ldots 1}_{(y+1)/2}\underbrace{0\ldots 0}_{(z+1)/2}\underbrace{1\ldots 1}_{(z-1)/2}$, and similarly for the other cases. Then this $S$ coincides on at most $n$ positions with any of the chosen $3$.

See http://www.artofproblemsolving.com/Forum/viewtopic.php?f=337&t=417447. Post #4 can be adapted to show $k = 3$ is not enough in this problem.