Team Selection Test for EGMO 2019

The answer is $64$. Assume that $n\ge 65$. Then there are at least $\left(\genfrac{}{}{0ex}{}{65}{2}\right)=2080$ unordered pairs of subsets $A_i,A_j$. By conditions, to each unordered pair $A_i,A_j$ we can correspond an element $c(i,j)\in S$ such that $c(i,j)\notin A_i\cup A_j$. Since $2080>2019$, for some $A_k,A_l$ and $A_p,A_q$ we have $c(k,l)=c(p,q)$. Finally, since at least three of the indices $k,l,p,q$ are distinct, the union of some three subsets is not equal to $S$, a contradiction.

Now let us give an example for $n=64$. Let $S=\{a_1,a_2,\dots ,a_{2019}\}$. There are $\left(\genfrac{}{}{0ex}{}{64}{2}\right)=2016$ unordered pairs of distinct indices $i,j$, $1\le i,j\le 64$. Let us fix any one-to-one correspondence between the set of $2016$ unordered pairs and the set $\{1,2,\dots ,2016\}$: $A_i,A_j\leftrightarrow m(i,j)\in \{1,2,\dots ,2016\}$. We start with $A_1=A_2=\cdots =A_{64}=S$ and after that for each $m(i,j)$ remove $a_{m(i,j)}$ from both $A_i$ and $A_j$. Since each element of $\{a_1,a_2,\dots ,a_{2016}\}$ is removed exactly from two subsets, the obtained collection $A_1,A_2,\dots ,A_{64}$ satisfies the conditions. Done.