Team selection test for 47. IMO

Solution:
Consider the following three element sets
$$\begin{aligned} N_{1} & = \left\{ \frac{p_{3} p_{4} \ldots p_{n-1}}{p_{1}}, \frac{p_{2} p_{3} \ldots p_{n-1}}{p_{1}}, \frac{p_{2} p_{3} \ldots p_{n-1} p_{n}}{p_{1}} \right\} \\ N_{2} & = \left\{ \frac{p_{1} p_{4} \ldots p_{n-1}}{p_{2}}, \frac{p_{1} p_{3} \ldots p_{n-1}}{p_{2}}, \frac{p_{1} p_{3} \ldots p_{n-1} p_{n}}{p_{2}} \right\} \\ & \vdots \\ N_{n-1} & = \left\{ \frac{p_{2} p_{3} \ldots p_{n-2}}{p_{n-1}}, \frac{p_{1} p_{2} \ldots p_{n-2}}{p_{n-1}}, \frac{p_{1} p_{2} \ldots p_{n-2} p_{n}}{p_{n-1}} \right\} \end{aligned}$$
It is easy to check that the union of these sets satisfies the condition of the problem and has $3n-3$ elements.

Suppose that there exists a set having $3n-2$ elements that satisfies the condition of the problem. It is clear that every prime number appears in denominator at most 3 times.

Let $M_{1} \subset M$ be the largest possible set of prime numbers which appear exactly three times in denominator and no two prime numbers from $M_{1}$ appear in one and the same denominator. Then the following inequality holds true
$$3|M_{1}| + 2(n - |M_{1}|) \geq 3n - 2$$
i.e. $|M_{1}| \geq n-2$.

Case 1. Let $|M_{1}| = n$. Then $N$ is a union of sets of the type $N_{i} = \left\{ \frac{a_{i}}{p_{i}}, \frac{b_{i}}{p_{i}}, \frac{c_{i}}{p_{i}} \right\}$ and it follows that $p_{i}$ does not appear in at most one of the numerators of the remaining fractions. In every $N_{i}$ there are at least two fractions whose numerators do not contain one $p_{j}$; otherwise there are two equal fractions. Therefore $2n \leq n$, a contradiction.

Case 2. Let $|M_{1}| = n-1$. There are two cases:

a) The set $N$ is a union of $n-1$ sets of the form $N_{i} = \left\{ \frac{a_{i}}{x p_{i}}, \frac{b_{i}}{p_{i}}, \frac{c_{i}}{p_{i}} \right\}$, where $x = 1$ or $x = p_{n}$ and $N_{n} = \left\{ \frac{r}{p_{n}}, \frac{s}{p_{n}} \right\}$. If a denominator of a fraction not in $N_{n}$ is divisible by $p_{n}$ then we have as above that $2(n-1) + 1 \leq n$, i.e. $n \leq 1$, a contradiction. Otherwise the denominators of at most three fractions are divisible by $p_{n}$. Therefore $2(n-1) + 1 \leq n-1 + 3$ implying $n \leq 3$. It is easy to be seen that $n=3$ gives no solution.

b) Consider the set $N_{n} = \left\{ \frac{t}{p_{n}} \right\}$. Then observations analogous to those in a) imply $2(n-1) \leq n-1 + 5$, i.e. $n \leq 6$. For every $n = 3,4,5,6$ it is easy to find an example of sets with $3n-2$ elements.

Case 3. Let $|M_{1}| = n-2$. To find a better $N$ one should have $n-2$ sets obtained by the primes from $M_{1}$ and two sets with two elements each obtained from $p_{n-1}$ and $p_{n}$. As above we obtain $2(n-2) + 2 \leq (n-2) + 3 + 3$, implying $n \leq 6$. Hence in this case we do not find a better $N$.

When $n = 3,4,5,6$ the answer is $3n-2$, and for $n \geq 7$ the answer is $3n-3$.