Problem 2136

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

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

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

$\boxed{1819}$