Maths Olympiad Prep

Library / /247 of 520

Combinatorics Difficulty 6.9 National olympiad Prove it

Let nn be a positive integer, and let S1,S2,,SnS_1,S_2,…,S_n be a collection of finite non-empty sets such that 1i<jnSiSjSiSj<1.\sum_{1\leq i<j\leq n}{\frac{|S_i \cap S_j|}{|S_i||S_j|}} <1.
Prove that there exist pairwise distinct elements x1,x2,,xnx_1,x_2,…,x_n such that xix_i is a member of SiS_i for each index ii.

Solution

1. Define the problem and the given condition:
We are given a collection of finite non-empty sets S1,S2,,Sn S_1, S_2, \ldots, S_n such that:
1i<jnSiSjSiSj<1. \sum_{1 \leq i < j \leq n} \frac{|S_i \cap S_j|}{|S_i||S_j|} < 1.
We need to prove that there exist pairwise distinct elements x1,x2,,xn x_1, x_2, \ldots, x_n such that xiSi x_i \in S_i for each i i .

2. Random selection and probability calculation:
Choose a random element xi x_i from Si S_i for each i=1,2,,n i = 1, 2, \ldots, n . The probability that the chosen elements xi x_i and xj x_j are the same for ij i \neq j is given by:
SiSjSiSj. \frac{|S_i \cap S_j|}{|S_i||S_j|}.

3. Summing the probabilities:
The probability that at least one pair (xi,xj) (x_i, x_j) are the same (i.e., there exists some ij i \neq j such that xi=xj x_i = x_j ) is at most:
1i<jnSiSjSiSj. \sum_{1 \leq i < j \leq n} \frac{|S_i \cap S_j|}{|S_i||S_j|}.
By the given condition, this sum is less than 1:
1i<jnSiSjSiSj<1. \sum_{1 \leq i < j \leq n} \frac{|S_i \cap S_j|}{|S_i||S_j|} < 1.

4. Conclusion using the probabilistic method:
Since the probability that some two xi x_i and xj x_j are the same is less than 1, there must exist a choice of x1,x2,,xn x_1, x_2, \ldots, x_n such that all xi x_i are distinct. This is because if the probability of an event is less than 1, then there exists a non-zero probability that the event does not occur. Hence, there exists a selection where all xi x_i are distinct.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.