
2. In a set of 20 elements there are $2 k+1$ different subsets of 7 elements such that each of these subsets intersects exactly $k$ other subsets. Find the maximum $k$ for which this is possible.

The answer is $k=2$.


Solution. Let $M$ be the set of residues mod20. An example is given by the sets $A_{i}=\{4 i+1,4 i+$ $2,4 i+3,4 i+4,4 i+5,4 i+6,4 i+7\} \subset M, i=0,1,2,3,4$.

Let $k \geq 2$. Obviously among any three 7-element subsets there are two intersecting subsets.

Let $A$ be any of the $2 k+1$ subsets. It intersects $k$ other subsets $B_{1}, \ldots, B_{k}$. The remaining subsets $C_{1}$, $\ldots, C_{k}$ do not intersect $A$ and are therefore pairwise intersecting. Since each $C_{i}$ intersects $k$ other subsets, it intersects exactly one $B_{j}$. This $B_{j}$ can not be the same for all $C_{i}$ because $B_{j}$ can not intersect $k+1$ subsets.

Thus there are two different $C_{i}$ intersecting different $B_{j}$; let $C_{1}$ intersect $B_{1}$ and $C_{2}$ intersect $B_{2}$. All the subsets that do not intersect $C_{1}$ must intersect each other; there is $A$ among them, therefore they are $A$ and all $B_{i}, i \neq 1$. Hence every $B_{j}$ and $B_{j}, i \neq 1, j \neq 1$, intersect. Applying the same argument to $C_{2}$ we see that any $B_{i}$ and $B_{j}, i \neq 2, j \neq 2$, intersect. We see that the family $A, B_{1}, \ldots, B_{k}$ contains only one pair, $B_{1}$ and $B_{2}$, of non-untersecting subsets, while $B_{1}$ intersects $C_{1}$ and $B_{2}$ intersects $C_{2}$. For each $i$ this list contains $k$ subsets intersecting $B_{i}$. It follows that no $C_{i}$ with $i>2$ intersects any $B_{j}$, that is, there are no such $C_{i}$, and $k \leq 2$.
