Saudi Arabian Mathematical Competitions

1) For $i \in \{1,2,3, \ldots, 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, \ldots, n\}$ then $|A_{i} \cup A_{j}| = 5 \Leftrightarrow |A_{i} \cap A_{j}| = 1$.

Suppose that $|S| = m$ and $S = \{a_{1}, a_{2}, \ldots, 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, \ldots, n\}$, $u \neq 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 \Leftrightarrow k = \frac{m-1}{2}$. This argument can be applied the same for $a_{2}, a_{3}, \ldots, 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
$$\binom{m}{2} = n \binom{3}{2} \Leftrightarrow 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
$$\binom{n}{2} = m \binom{(m-1)/2}{2} \Leftrightarrow 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}, \ldots, 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, \ldots, n\}$. If there is some index $k \in \{5,6, \ldots, 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} \neq a$ for all $i = 1,2,3,4$ and $x_{i} \neq x_{j}$ for $i \neq j$ since all sets $A_{1}, A_{2}, A_{3}, A_{4}$ contain $a$. This implies that $|A_{k}| \geq 4$, which is a contradiction.

Hence, all sets $A_{1}, A_{2}, \ldots, 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, \ldots, m\}$ and $n$ subsets $A_{1}, A_{2}, \ldots, 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 \neq 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}, \ldots, A_{n}$ and $m = (k-1)n + 1$.

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