I have a set $S$ of sequences of zeros and ones (the sequence length is $2^n-1$). I need to know if there is a condition on the number of elements of $S$ which will imply the existence of two sequences in $S$ having an intersection of at least $k$ elements. (They have the same entries in at least $k$ positions.)
(Basically, I would like to know how large $|S|$ should be to make sure that at least two sequences are identical in $k$ positions.)
Thanks a lot in advance,
Let me reformulate, what we want is equivalent as the maximal size of subset of $\mathbb{F}_2^n$ on which each pair of elements have at most $k-1$ same digits.
I think youem is right in the case $n \geqslant 3(k-1)$, if you have at least 3 elements in $S = \{u,v,w, \dots \}$, there are $n-k+1$ different integers $i $ such that $u_i \neq v_i$. Necessarily we have for those $i$'s $w_i \in \{ u_i, v_i\} = \mathbb{F}_2$. Let us say that we have $r<k$ indexes on which $w$ takes the values of $u$ and $s<k$ on which it takes the value of $v$. We have $r + s = n-k+1 \leqslant 2k-2$ so $n \leqslant 3(k-1)$. So in this particular case we have $|S| > 2$ as a condition, maybe it is a hint: the condition may involve the binomial coefficient $\binom{3k -4}{n}$.
If you check some references about correcting codes, you might find what you want (hamming distance with distance k or k-1).