Maximum odd number of subsets, each intersects exactly half of the others Find the largest positive integer $k$ with the following property $-$ there exist $2k+1$ distinct subsets of $\{1,\ldots,20\}$ such that each such subset intersects precisely $k$ of the other $2k$ subsets.
The original problem I saw also insisted on each set to have $7$ elements (which makes things much easier $-$ it is easy to obtain $k\leq 2$) but what would happen if the do not have such a restriction?
I cannot obtain anything apart from the fact that $k$ is even (since the number of intersecting pairs is $\frac{k(2k+1)}{2}$). Any help appreciated!
 A: Not an answer, but too long for a comment.
First, here's a graph-theoretic interpretation.  Define a graph with a node for each subset of $\{1,\dots,n\}$ and an edge for each pair of distinct nodes that have nonempty intersection. The problem is to find a largest subset $S$ of nodes such that both the subgraph induced by $S$ and its complement are $k$-regular.
Now here's an integer linear programming formulation.  Let $N_i$ be the set of neighbors of node $i$, and let $\overline{k}=(2^n-1)/2$ be an upper bound on integer decision variable $k$.  Let binary decision variable $x_i$ indicate whether node $i$ is selected.  The problem is to maximize $k$ subject to
\begin{align}
\sum_i x_i &= 2k+1\\
-\overline{k}(1-x_i) \le \sum_{j \in N_i} x_j - k &\le |N_i|(1-x_i) &\text{for all $i$}\\
k &\in [0, \overline{k}] \cap \mathbb{Z}
\end{align}
The first constraint specifies that $2k+1$ nodes are selected.  The second "big-M" constraint enforces the implication $x_i=1 \implies \sum_{j \in N_i} x_j = k$. That is, if node $i$ is selected then exactly $k$ of its neighbors are also selected.  The third constraint enforces bounds and integrality of $k$.  The optimal values reported above for $n\in\{1,\dots,9\}$ were obtained by solving this formulation.
