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.2n+1 numbers whose prime divisors are all taken from a set of n. So each number can be written as p1r1...pnrn for some non-negative integers ri, where pi is the set of prime factors common to all the numbers. We classify each ri as even or odd. That gives 2n possibilities. But there are more than 2n + 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 2n + 1, so we can find another pair. We may repeat to find 2n + 1 pairs with a square product. [After removing 2n pairs, there are still 2n + 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 59 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