Difference between revisions of "1985 IMO Problems/Problem 4"
(→Solution) |
|||
| Line 6: | Line 6: | ||
==See also== | ==See also== | ||
| + | == See Also == {{IMO box|year=1985|num-b=3|num-a=5}} | ||
| + | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
Latest revision as of 22:56, 29 January 2021
Contents
Problem
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.
Solution
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.
See also
See Also
| 1985 IMO (Problems) • Resources | ||
| Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
| All IMO Problems and Solutions | ||
