Given a set $S$ of $n$ elements. Let $T$ be the set of all subsets of $S$, with size $\frac{n}{2}$ ($n$ is even). We want to select a subset $T'$ of $T$, with the property that for any pair of the elements $x,y \in S$, there exists a subset $Q \in T'$, such that $x \in Q$ and $y \in Q$. What is the minimum size of $T'$? In particular, is $|T'| < n$?



Selecting subsets with size $\frac{n}{2}$ covering every pair of the elements
The answer is $6$ for $n \ge 4$. This is problem 1.3 on IMC 2013:


<http://www.imc-math.org.uk/imc2013/IMC2013-day1-solutions.pdf>




---


It takes $6$ subsets. 


Lower bound: For any element $a$, to cover all $n-1 \gt 2(n/2 -1)$ pairs of elements including $a$, there must be at least $3$ subsets containing $a$. This is true for all elements so there must be at least $3n$ pairs $(e,Q), e\in Q$. Each subset contributes $n/2$ pairs $(e,Q), e \in Q$ so there must be at least $6$.


Construction: Write $n/2$ as $2s+3t$ with $s,t$ nonnegative integers. Break the elements into sets $A,B,C,D$ of size $s$ and $X',X'',Y',Y'',Z',Z''$ of size $t$, with $X= X' \cup X'', Y=Y'\cup Y'',Z = Z' \cup Z''$. Then consider the unions of $\{A,B,X,Y'\},$ $\{C,D,X,Y''\},$ $\{A,C,Y,Z'\},$ $\{B,D,Y,Z''\},$ $\{A,D,Z,X'\},$ and $\{B,C,Z,X''\}.$


