Given a set M of 1985 distinct positive integers, none of which has a prime divisor greater than 23, prove that M contains a subset of 4 elements whose product is the 4th power of an integer.

**Solution**

Suppose we have a set of at least 3.2^{n}+1 numbers whose prime divisors are all taken from a set of n. So each number can be written as p_{1}^{r1}...p_{n}^{rn} for some non-negative integers r_{i}, where p_{i} is the set of prime factors common to all the numbers. We classify each r_{i} as even or odd. That gives 2^{n} possibilities. But there are more than 2^{n} + 1 numbers, so two numbers have the same classification and hence their product is a square. Remove those two and look at the remaining numbers. There are still more than 2^{n} + 1, so we can find another pair. We may repeat to find 2^{n} + 1 pairs with a square product. [After removing 2^{n} pairs, there are still 2^{n} + 1 numbers left, which is just enough to find the final pair.] But we may now classify these pairs according to whether each exponent in the square root of their product is odd or even. We must find two pairs with the same classification. The product of these four numbers is now a fourth power.

Applying this to the case given, there are 9 primes less than or equal to 23 (2, 3, 5, 7, 11, 13, 17, 19, 23), so we need at least 3.512 + 1 = 1537 numbers for the argument to work (and we have 1985).

The key is to find the 4th power in two stages, by first finding lots of squares. If we try to go directly to a 4th power, this type of argument does not work (we certainly need more than 5 numbers to be sure of finding four which sum to 0 mod 4, and 5^{9} is far too big).

Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

© John Scholes

jscholes@kalva.demon.co.uk

22 Oct 1998