# Choosing subsets with half the elements in common

Let $S=\lbrace 1,2,3,\ldots, 2^n\rbrace$ for some $n\ge 2$. What is the maximum cardinality of a set $S'$ of $2^{n-1}$-element subsets of $S$ such that every pair of elements of $S'$ has exactly $2^{n-2}$ elements in common?

The answer might be $2^n - 1$. This problem came up a while ago while I was working on something larger. I skirted around it, but it always bugged me.

-
Certainly Hadamard designs (related to Hadamard matrices) will give that as a lower bound. If you view it as a combinatorial linear algebra problem, I think that will give you an exact answer. Gerhard "Don't Ask For Linear Algebra" Paseman, 2013.03.27 – Gerhard Paseman Mar 27 '13 at 17:04
Look up Frankl--Wilson, and Ray--Chaudhury--Wilson theorems. – Boris Bukh Mar 27 '13 at 17:41

1. Suppose the desired number is $m - 1$.
2. Fill in the top row of an $m\times 2^n$ matrix with all $1$.
3. Each subsequent row represents an element of $S'$. If $i$ is in the $j^{th}$ element of $S'$, then the matrix entry $(j+1,i)$ is $1$, and otherwise $-1$.
6. The largest linearly independent set has cardinality equal to the dimension, which here is $2^n$ since that is the length of our row vectors.
7. Thus our number is $m-1=2^n -1$.