Problem 9. Let $n \geq 3$ be a positive integer and $M$ be the set of the first $n$ prime numbers. For every nonempty subset $X$ of $M$ denote by $P(X)$ the product of the elements of $X$. Let $N$ be a set of fractions of the form $\frac{P(A)}{P(B)}$, where $A \subset M, B \subset M, A \cap B=\phi$ such that the product of any 7 elements of $N$ is an integer. What is the maximum possible cardinality of $N$ ?

Alexander Ivanov
9. 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 $3 n-3$ elements.

Suppose that there exists a set having $3 n-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\left|M_{1}\right|+2\left(n-\left|M_{1}\right|\right) \geq 3 n-2
$$

i.e. $\left|M_{1}\right| \geq n-2$.

Case 1. Let $\left|M_{1}\right|=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 nominators of the remaining fractions. In every $N_{i}$ there are at least two fractions whose nominators do not contain one $p_{j}$; otherwise there are two equal fractions. Therefore $2 n \leq n$, a contradiction.

Case 2. Let $\left|M_{1}\right|=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 fraction 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 $3 n-2$ elements.

Case 3. Let $\left|M_{1}\right|=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 $3 n-2$, and for $n \geq 7$ the answer is $3 n-3$.