Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(page/ problem/ solution)
 
 
(3 intermediate revisions by 2 users not shown)
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.
  
−
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.
+
==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 <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 == {{IMO box|year=1985|num-b=3|num-a=5}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 22: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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_IMO_Problems/Problem_4&oldid=144023"