1) For i∈{1,2,3,…,n}, denote Ai as the set of roots of Pi(x) then since the given condition, we can see that ∣Ai∣=3 and for all i,j∈{1,2,3,…,n} then ∣Ai∪Aj∣=5⇔∣Ai∩Aj∣=1.
Suppose that ∣S∣=m and S={a1,a2,…,am}. Denote k as the number of sets Ai that contain a1 then we will count #(u,v) in which u∈S, v∈{1,2,3,…,n}, u=a1 and u∈Av, a1∈Av.
- Choose u first, we have #(u,v)=(m−1)⋅1.
- Choose v first, we have #(u,v)=k⋅2.
Then 2k=m−1⇔k=2m−1. This argument can be applied the same for a2,a3,…,am so for all ai∈S, there are exactly 2m−1 sets Ai that contain ai.
Then by counting #(ai,aj,Ak) such that ai∈Ak, aj∈Ak we have
(2m)=n(23)⇔m(m−1)=3n.
By counting #(Ai,Aj,ak) such that ak∈Ai, ak∈Aj we have
(2n)=m(2(m−1)/2)⇔n(n−1)=m⋅2m−1⋅2m−3.
By solving this system of equations, we have m=n=7.
2) For n>7, denote A1={a,b,c} and by pigeonhole principle, there is some element of A1 that appears in at least 3 sets among A2,A3,…,An. Without loss of generality, we can suppose that a∈A2,A3,A4. We shall prove that a∈Ai for all i∈{1,2,3,…,n}. If there is some index k∈{5,6,…,n} with a∈/Ak then we can write Ak∩Ai={xi} for i=1,2,3,4.
It is clear to check that xi=a for all i=1,2,3,4 and xi=xj for i=j since all sets A1,A2,A3,A4 contain a. This implies that ∣Ak∣≥4, which is a contradiction.
Hence, all sets A1,A2,…,An share one common element a. This means
∣S∣=∣A1∪A2∪A3∪⋯∪An∣=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,…,m} and n subsets A1,A2,…,An of S such that ∣Ai∣=k for i=1,n. Suppose that ∣Ai∪Aj∣=1 for all i=j.
1. If for each a,b∈S, there is exactly 1 subset Ai such that a,b∈Ai then m=n=k2−k+1.
2. If n>k2−k+1 then there is exactly 1 element a∈S that appears in all sets A1,A2,…,An and m=(k−1)n+1.
The way to solve this problem is the same as the solution for the original problem.