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 (→‎Solution: typo or Freudian slip)
m
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 integers 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> \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?
  
 
(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>\displaystyle n>2</math> is there exactly one set having the stated property?
Line 7: Line 7:
 
== Solution ==
 
== Solution ==
  
−
Let <math> k = \prod p_i^{e_i} </math> be the greatest element of the set.  Then <math>\displaystyle k</math> divides the least common multiple of the other elements of the set [[iff]]. the set has [[cardinality]] of 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>\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.
  
 
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> \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.

Revision as of 16:09, 29 October 2006

Problem

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

(b) For which values of $\displaystyle 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 $\displaystyle k$ divides the least common multiple of the other elements of the set if and only if the set has cardinality at least $\displaystyle \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 $\displaystyle n > 3$, we may let $\displaystyle k = \mbox{lcm} (n-1, n-2) = (n-1)(n-2)$, since all the $\displaystyle p_i^{e_i}$ must clearly be less than $\displaystyle n$ and this product must also be greater than $\displaystyle n$ if $\displaystyle n$ is at least 4. For $\displaystyle n > 4$, we may also let $\displaystyle k = \mbox{lcm} (n-2, n-3) = (n-2)(n-3)$, for the same reasons. However, for $\displaystyle n = 4$, this does not work, and indeed no set works other than $\displaystyle \{ 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.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_4&oldid=10491"