Maths Olympiad Prep

Library / /2 of 4

, 2020

Number theory Difficulty 7.8 National olympiad, round 2 Prove it Netherlands

A set SS consisting of 20192019 (distinct) positive integers has the following property: the product of any 100100 elements of SS is a divisor of the product of the other 19191919 elements. What is the maximum number of prime numbers that SS could contain?

Solution

We start with the construction. Choose distinct primes p1,p2,,p1819p_1, p_2, \dots, p_{1819}, and let P=p1p2p1819P = p_1p_2\cdots p_{1819}. Let
S={p1,p2,,p1819,P,Pp1,,Pp199}. S = \{p_1, p_2, \dots, p_{1819}, P, P \cdot p_1, \dots, P \cdot p_{199}\}.
For each pip_i, there are 201201 numbers in SS that are divisible by pip_i (namely, pip_i and all multiples of PP). Of these, at most one has two factors pip_i; the rest has only one factor pip_i. If we now take 100100 numbers from SS, then their product has at most 101101 factors pip_i. The other numbers contain at least 101101 numbers which are divisible by pip_i, hence their product has at least 101101 factors pip_i. Because this holds for any pip_i, and the numbers in SS do not have any other prime factors, this implies that SS has the desired property.

We now prove that SS cannot contain more than 18191819 primes. Consider a prime divisor qq of a number in SS. Suppose that at most 199199 numbers SS are divisible by qq. Then we take the 100100 elements of SS having the most factors qq; these always have more factors qq in total than the other elements, which contradicts the condition in the problem statement. Hence, there are at least 200200 numbers in SS which are divisible by qq. If there are exactly 200200, then we also get that the number of factors qq in all of these numbers must be equal, otherwise we get a contradiction again by taking the 100100 elements having the most factors qq.

We see that SS contains at least 199199 non-primes, because a prime pp in SS divides at least 199199 other elements of SS. Suppose that SS contains exactly 199199 non-primes. Then the prime factor pp in each of these 199199 non-primes occurs exactly once (namely, equally often as in the prime number pp). Moreover, the numbers in SS cannot be divisible by a prime rr that is not contained in SS, because then there would be at least 200200 multiples of rr inside SS, and these would be 200200 non-primes, which is a contradiction. We get that each of the 199199 non-primes in SS must be the product of the primes in SS. In particular, these 199199 numbers are not distinct. This is a contradiction, hence SS must contain at least 200200 non-primes, and hence at most 18191819 primes.

1819\boxed{1819}

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.