SAUDI ARABIAN MATHEMATICAL COMPETITIONS

1) For $i\in \{1,2,3,\dots ,n\}$, denote $A_i$ as the set of roots of $P_i(x)$ then since the given condition, we can see that $|A_i|=3$ and for all $i,j\in \{1,2,3,\dots ,n\}$ then $|A_i\cup A_j|=5\iff |A_i\cap A_j|=1$.

Suppose that $|S|=m$ and $S=\{a_1,a_2,\dots ,a_m\}$. Denote $k$ as the number of sets $A_i$ that contain $a_1$ then we will count $\#(u,v)$ in which $u\in S$, $v\in \{1,2,3,\dots ,n\}$, $u\ne a_1$ and $u\in A_v$, $a_1\in A_v$.

- Choose $u$ first, we have $\#(u,v)=(m-1)\cdot 1$. - Choose $v$ first, we have $\#(u,v)=k\cdot 2$.

Then $2k=m-1\iff k=\frac{m-1}{2}$. This argument can be applied the same for $a_2,a_3,\dots ,a_m$ so for all $a_i\in S$, there are exactly $\frac{m-1}{2}$ sets $A_i$ that contain $a_i$.

Then by counting $\#(a_i,a_j,A_k)$ such that $a_i\in A_k$, $a_j\in A_k$ we have $$\left(\genfrac{}{}{0ex}{}{m}{2}\right)=n\left(\genfrac{}{}{0ex}{}{3}{2}\right)\iff m(m-1)=3n.$$

By counting $\#(A_i,A_j,a_k)$ such that $a_k\in A_i$, $a_k\in A_j$ we have $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=m\left(\genfrac{}{}{0ex}{}{(m-1)/2}{2}\right)\iff n(n-1)=m\cdot \frac{m-1}{2}\cdot \frac{m-3}{2}.$$

By solving this system of equations, we have $m=n=7$.

2) For $n>7$, denote $A_1=\{a,b,c\}$ and by pigeonhole principle, there is some element of $A_1$ that appears in at least 3 sets among $A_2,A_3,\dots ,A_n$. Without loss of generality, we can suppose that $a\in A_2,A_3,A_4$. We shall prove that $a\in A_i$ for all $i\in \{1,2,3,\dots ,n\}$. If there is some index $k\in \{5,6,\dots ,n\}$ with $a\notin A_k$ then we can write $A_k\cap A_i=\{x_i\}$ for $i=1,2,3,4$.

It is clear to check that $x_i\ne a$ for all $i=1,2,3,4$ and $x_i\ne x_j$ for $i\ne j$ since all sets $A_1,A_2,A_3,A_4$ contain $a$. This implies that $|A_k|\ge 4$, which is a contradiction.

Hence, all sets $A_1,A_2,\dots ,A_n$ share one common element $a$. This means $$|S|=|A_1\cup A_2\cup A_3\cup \cdots \cup A_n|=1+n(3-1)=2n+1.$$

In general, we can state this problem as follows: For integers $m,n,k>1$, we consider $S=\{1,2,3,\dots ,m\}$ and $n$ subsets $A_1,A_2,\dots ,A_n$ of $S$ such that $|A_i|=k$ for $i=\overline{1,n}$. Suppose that $|A_i\cup A_j|=1$ for all $i\ne j$.

1. If for each $a,b\in S$, there is exactly 1 subset $A_i$ such that $a,b\in A_i$ then $m=n=k^2-k+1$. 2. If $n>k^2-k+1$ then there is exactly 1 element $a\in S$ that appears in all sets $A_1,A_2,\dots ,A_n$ and $m=(k-1)n+1$.

The way to solve this problem is the same as the solution for the original problem.