1985 IMO Problems/Problem 4
Given a set of distinct positive integers, none of which has a prime divisor greater than , prove that contains a subset of elements whose product is the th power of an integer.
We have that . We need only consider the exponents. First, we consider the number of subsets of two elements, such that their product is a perfect square. There are different parity cases for the exponents . Thus, we have at least one pair of elements out of elements. Removing these two elements yields elements. By applying the Pigeon Hole Principle again, we find that there exists another such subset. Continuing on like this yields at least pairs of elements of whose product is a perfect square. Let be the set of the square roots of the products of each pair. Then, by the Pigeon Hole Principle again, there exist at least two elements whose product is a perfect square. Let the elements be and let where . Then, we have for some which implies and the claim is proved.
|1985 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|