Difference between revisions of "1985 IMO Problems/Problem 4"

 
(2 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==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 <math>S</math> 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 <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==
 
==See also==
[[Category:Olympiad Number Theory problems]]
+
== See Also == {{IMO box|year=1985|num-b=3|num-a=5}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 23:56, 29 January 2021

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 $S$ 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 $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

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