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 11:04, 25 August 2008

Problem

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 $4$th power of an integer.

Solution

We have that $x\in M\Rightarrow x=2^{e_1}3^{e_2}\cdots 19^{e_8}23^{e_9}$. 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 $2^9=512$ different parity cases for the exponents $e_1,e_2,...,e_9$. Thus, we have at least one pair of elements out of $1985$ elements. Removing these two elements yields $1983$ elements. By applying the Pigeon Hole Principle again, we find that there exists another such subset. Continuing on like this yields at least $734$ pairs of elements of $M$ whose product is a perfect square. Let the $S$ 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 $x,y$ and let $x=\sqrt{ab},y=\sqrt{cd}$ where $a,b,c,d\in M$. Then, we have $xy=z^2$ for some $z$ which implies $abcd=z^4$ and the claim is proved.

See also