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 "1981 IMO Problems/Problem 4"

m
(template)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
(a) For which values of <math> \displaystyle n>2</math> is there a [[set]] of <math>\displaystyle n</math> consecutive [[positive integer]]s such that the largest number in the set is a [[divisor]] of the [[least common multiple]] of the remaining <math>\displaystyle n-1</math> numbers?
+
(a) For which values of <math>n>2</math> is there a [[set]] of <math>n</math> consecutive [[positive integer]]s such that the largest number in the set is a [[divisor]] of the [[least common multiple]] of the remaining <math>n-1</math> numbers?
  
−
(b) For which values of <math>\displaystyle n>2</math> is there exactly one set having the stated property?
+
(b) For which values of <math>n>2</math> is there exactly one set having the stated property?
  
 
== Solution ==
 
== Solution ==
  
−
Let <math> k = \prod p_i^{e_i} </math> be the greatest element of the set, written in its [[prime factorization]].  Then <math>\displaystyle k</math> divides the least common multiple of the other elements of the set if and only if the set has [[cardinality]] at least <math>\displaystyle \max \{ p_i^{e_i} \}</math>, since for any of the <math>p_i^{e_i}</math>, we must go down at least to <math>k-p_i^{e_i}</math> to obtain another [[multiple]] of <math>p_i^{e_i}</math>.  In particular, there is no set of cardinality 3 satisfying our conditions, because each number greater than or equal to 3 must be divisible by a number that is greater than two and is a power of a prime.
+
Let <math> k = \prod p_i^{e_i} </math> be the greatest element of the set, written in its [[prime factorization]].  Then <math>k</math> divides the least common multiple of the other elements of the set if and only if the set has [[cardinality]] at least <math>\max \{ p_i^{e_i} \}</math>, since for any of the <math>p_i^{e_i}</math>, we must go down at least to <math>k-p_i^{e_i}</math> to obtain another [[multiple]] of <math>p_i^{e_i}</math>.  In particular, there is no set of cardinality 3 satisfying our conditions, because each number greater than or equal to 3 must be divisible by a number that is greater than two and is a power of a prime.
  
−
For <math> \displaystyle n > 3 </math>, we may let <math> \displaystyle k = \mbox{lcm} (n-1, n-2) = (n-1)(n-2) </math>, since all the <math>\displaystyle p_i^{e_i}</math> must clearly be less than <math>\displaystyle n</math> and this product must also be greater than <math>\displaystyle n</math> if <math>\displaystyle n</math> is at least 4.  For <math> \displaystyle n > 4 </math>, we may also let <math> \displaystyle k = \mbox{lcm} (n-2, n-3) = (n-2)(n-3)</math>, for the same reasons.  However, for <math> \displaystyle n = 4 </math>, this does not work, and indeed no set works other than <math> \displaystyle \{ 3,4,5,6 \} </math>.  To prove this, we simply note that for any integer not equal to 6 and greater than 4 must have some power-of-a-prime factor greater than 3.
+
For <math>n > 3 </math>, we may let <math>k = \mbox{lcm} (n-1, n-2) = (n-1)(n-2) </math>, since all the <math>p_i^{e_i}</math> must clearly be less than <math>n</math> and this product must also be greater than <math>n</math> if <math>n</math> is at least 4.  For <math>n > 4 </math>, we may also let <math>k = \mbox{lcm} (n-2, n-3) = (n-2)(n-3)</math>, for the same reasons.  However, for <math>n = 4 </math>, this does not work, and indeed no set works other than <math>\{ 3,4,5,6 \} </math>.  To prove this, we simply note that for any integer not equal to 6 and greater than 4 must have some power-of-a-prime factor greater than 3.
  
 
Q.E.D.
 
Q.E.D.
Line 15: Line 15:
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
{{IMO box|num-b=3|num-a=5|year=1981}}
−
 
 
−
* [[1981 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366641#p366641 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 19:46, 25 October 2007

Problem

(a) For which values of $n>2$ is there a set of $n$ consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining $n-1$ numbers?

(b) For which values of $n>2$ is there exactly one set having the stated property?

Solution

Let $k = \prod p_i^{e_i}$ be the greatest element of the set, written in its prime factorization. Then $k$ divides the least common multiple of the other elements of the set if and only if the set has cardinality at least $\max \{ p_i^{e_i} \}$, since for any of the $p_i^{e_i}$, we must go down at least to $k-p_i^{e_i}$ to obtain another multiple of $p_i^{e_i}$. In particular, there is no set of cardinality 3 satisfying our conditions, because each number greater than or equal to 3 must be divisible by a number that is greater than two and is a power of a prime.

For $n > 3$, we may let $k = \mbox{lcm} (n-1, n-2) = (n-1)(n-2)$, since all the $p_i^{e_i}$ must clearly be less than $n$ and this product must also be greater than $n$ if $n$ is at least 4. For $n > 4$, we may also let $k = \mbox{lcm} (n-2, n-3) = (n-2)(n-3)$, for the same reasons. However, for $n = 4$, this does not work, and indeed no set works other than $\{ 3,4,5,6 \}$. To prove this, we simply note that for any integer not equal to 6 and greater than 4 must have some power-of-a-prime factor greater than 3.

Q.E.D.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1981 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=1981_IMO_Problems/Problem_4&oldid=18776"