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.



Choosing subsets with half the elements in common
To flesh out the Hadamard matrix proof:


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$.
4. The rows are orthogonal to each other.
5. Orthogonal sets are linearly independent.
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$.
8. Not too hard to show that such a matrix exists. For example, see Sylvester's construction <http://en.wikipedia.org/wiki/Hadamard_matrix#Sylvester.27s_construction>


