Difference between revisions of "1985 IMO Problems/Problem 4"
(page/ problem/ solution) |
|||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
Given a set <math>M</math> of <math>1985</math> distinct positive integers, none of which has a prime divisor greater than <math>23</math>, prove that <math>M</math> contains a subset of <math>4</math> elements whose product is the <math>4</math>th power of an integer. | Given a set <math>M</math> of <math>1985</math> distinct positive integers, none of which has a prime divisor greater than <math>23</math>, prove that <math>M</math> contains a subset of <math>4</math> elements whose product is the <math>4</math>th power of an integer. | ||
+ | ==Solution== | ||
We have that <math>x\in M\Rightarrow x=2^{e_1}3^{e_2}\cdots 19^{e_8}23^{e_9}</math>. 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 <math>2^9=512</math> different parity cases for the exponents <math>e_1,e_2,...,e_9</math>. Thus, we have at least one pair of elements out of <math>1985</math> elements. Removing these two elements yields <math>1983</math> elements. By applying the Pigeon Hole Principle again, we find that there exists another such subset. Continuing on like this yields at least <math>734</math> pairs of elements of <math>M</math> whose product is a perfect square. Let the <math>S</math> be the set of the square root of the product 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 <math>x,y</math> and let <math>x=\sqrt{ab},y=\sqrt{cd}</math> where <math>a,b,c,d\in M</math>. Then, we have <math>xy=z^2</math> for some <math>z</math> which implies <math>abcd=z^4</math> and the claim is proved. | We have that <math>x\in M\Rightarrow x=2^{e_1}3^{e_2}\cdots 19^{e_8}23^{e_9}</math>. 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 <math>2^9=512</math> different parity cases for the exponents <math>e_1,e_2,...,e_9</math>. Thus, we have at least one pair of elements out of <math>1985</math> elements. Removing these two elements yields <math>1983</math> elements. By applying the Pigeon Hole Principle again, we find that there exists another such subset. Continuing on like this yields at least <math>734</math> pairs of elements of <math>M</math> whose product is a perfect square. Let the <math>S</math> be the set of the square root of the product 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 <math>x,y</math> and let <math>x=\sqrt{ab},y=\sqrt{cd}</math> where <math>a,b,c,d\in M</math>. Then, we have <math>xy=z^2</math> for some <math>z</math> which implies <math>abcd=z^4</math> and the claim is proved. | ||
+ | |||
+ | ==See also== | ||
+ | [[Category:Olympiad Number Theory problems]] |
Revision as of 12:04, 25 August 2008
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 the
be the set of the square root of the product 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.