Maths Olympiad Prep

Library / /148 of 155

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Saudi Arabia

For integer n>1n > 1, consider nn cube polynomials P1(x),,Pn(x)P_{1}(x), \ldots, P_{n}(x) such that each polynomial has 3 distinct real roots. Denote SS as the set of roots of the following equation
P1(x)P2(x)P3(x)Pn(x)=0. P_{1}(x) P_{2}(x) P_{3}(x) \ldots P_{n}(x) = 0.
It is also known that for each 1i<jn1 \leq i < j \leq n, Pi(x)Pj(x)=0P_{i}(x) P_{j}(x) = 0 has 5 distinct real roots.

1. Prove that if for each a,bSa, b \in S, there is exactly one i{1,2,3,,n}i \in \{1,2,3, \ldots, n\} such that Pi(a)=Pi(b)=0P_{i}(a) = P_{i}(b) = 0 then n=7n = 7.

2. Prove that if n>7n > 7 then S=2n+1|S| = 2n + 1.

Solution

1) For i{1,2,3,,n}i \in \{1,2,3, \ldots, n\}, denote AiA_{i} as the set of roots of Pi(x)P_{i}(x) then since the given condition, we can see that Ai=3|A_{i}| = 3 and for all i,j{1,2,3,,n}i, j \in \{1,2,3, \ldots, n\} then AiAj=5AiAj=1|A_{i} \cup A_{j}| = 5 \Leftrightarrow |A_{i} \cap A_{j}| = 1.

Suppose that S=m|S| = m and S={a1,a2,,am}S = \{a_{1}, a_{2}, \ldots, a_{m}\}. Denote kk as the number of sets AiA_{i} that contain a1a_{1} then we will count #(u,v)\#(u, v) in which uSu \in S, v{1,2,3,,n}v \in \{1,2,3, \ldots, n\}, ua1u \neq a_{1} and uAvu \in A_{v}, a1Ava_{1} \in A_{v}.

- Choose uu first, we have #(u,v)=(m1)1\#(u, v) = (m-1) \cdot 1.
- Choose vv first, we have #(u,v)=k2\#(u, v) = k \cdot 2.

Then 2k=m1k=m122k = m-1 \Leftrightarrow k = \frac{m-1}{2}. This argument can be applied the same for a2,a3,,ama_{2}, a_{3}, \ldots, a_{m} so for all aiSa_{i} \in S, there are exactly m12\frac{m-1}{2} sets AiA_{i} that contain aia_{i}.

Then by counting #(ai,aj,Ak)\#(a_{i}, a_{j}, A_{k}) such that aiAka_{i} \in A_{k}, ajAka_{j} \in A_{k} we have
(m2)=n(32)m(m1)=3n. \binom{m}{2} = n \binom{3}{2} \Leftrightarrow m(m-1) = 3n.

By counting #(Ai,Aj,ak)\#(A_{i}, A_{j}, a_{k}) such that akAia_{k} \in A_{i}, akAja_{k} \in A_{j} we have
(n2)=m((m1)/22)n(n1)=mm12m32. \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=7m = n = 7.

2) For n>7n > 7, denote A1={a,b,c}A_{1} = \{a, b, c\} and by pigeonhole principle, there is some element of A1A_{1} that appears in at least 3 sets among A2,A3,,AnA_{2}, A_{3}, \ldots, A_{n}. Without loss of generality, we can suppose that aA2,A3,A4a \in A_{2}, A_{3}, A_{4}. We shall prove that aAia \in A_{i} for all i{1,2,3,,n}i \in \{1,2,3, \ldots, n\}. If there is some index k{5,6,,n}k \in \{5,6, \ldots, n\} with aAka \notin A_{k} then we can write AkAi={xi}A_{k} \cap A_{i} = \{x_{i}\} for i=1,2,3,4i = 1,2,3,4.

It is clear to check that xiax_{i} \neq a for all i=1,2,3,4i = 1,2,3,4 and xixjx_{i} \neq x_{j} for iji \neq j since all sets A1,A2,A3,A4A_{1}, A_{2}, A_{3}, A_{4} contain aa. This implies that Ak4|A_{k}| \geq 4, which is a contradiction.

Hence, all sets A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} share one common element aa. This means
S=A1A2A3An=1+n(31)=2n+1. |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>1m, n, k > 1, we consider S={1,2,3,,m}S = \{1,2,3, \ldots, m\} and nn subsets A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} of SS such that Ai=k|A_{i}| = k for i=1,ni = \overline{1, n}. Suppose that AiAj=1|A_{i} \cup A_{j}| = 1 for all iji \neq j.

1. If for each a,bSa, b \in S, there is exactly 1 subset AiA_{i} such that a,bAia, b \in A_{i} then m=n=k2k+1m = n = k^{2} - k + 1.
2. If n>k2k+1n > k^{2} - k + 1 then there is exactly 1 element aSa \in S that appears in all sets A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} and m=(k1)n+1m = (k-1)n + 1.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.