Skip to main content
1 of 4
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

For even $n=2k$, one cannot get more than $N:=\binom{k}{2}$ sets.

Proof. Observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $0$ or $1$ elements. However, the maximum size of such a family is $k-1$ (achieved by a pencil), which is a contradiction.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187