IMO 1994 SL N3

Origin: FIN | Category: Number Theory

Problem

Find a set A of positive integers such that for any infinite set P of prime numbers, there exist positive integers m \inA and n ̸\inA, both the product of the same number of distinct elements of P.

Solution

Let A be the set of all numbers of the form p1p2 . . . pp1, where p1 < p2 < \cdot \cdot \cdot < pp1 are primes. In other words, A = {2 \cdot 3, 2 \cdot 5, . . . } \cup{3 \cdot 5 \cdot 7, 3 \cdot 5 \cdot 11, . . . } \cup{5 \cdot 7 \cdot 11 \cdot 13 \cdot 17, . . . } \cup\cdot \cdot \cdot . This set satisfies the requirements of the problem. Indeed, for any infinite set of primes P = {q1, q2, . . . } (where q1 < q2 < \cdot \cdot \cdot ) we have m = q1q2 \cdot \cdot \cdot qq1 \inA and n = q2q3 \cdot \cdot \cdot qq1+1 ̸\inA.