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"

 
(→‎Alternate Solution)
 
(5 intermediate revisions by 4 users not shown)
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>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.  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 conidtions, because each number greater than or equal two 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.
  
−
{{alternate solutions}}
+
== Alternate Solution ==
 +
Let, for some <math>n</math> and <math>m</math> with <math>m>n</math>, <math>m\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)\ |\ (m-1)(m-2)\cdots(m-n+1)</math>.
  
−
== Resources ==
+
We can trivially check that, there is no such <math>m</math> for <math>n=3</math>, only <math>m=3</math> works for <math>n=4</math> and <math>m=3,8</math> works for <math>n=5</math>.
  
−
* [[1981 IMO Problems]]
+
Now, consider, <math>n>5</math>. By [http://en.wikipedia.org/wiki/Bertrand's_postulate Bertrand's postulate] there is a prime <math>p</math> such that <math>2 \le \left\lfloor\frac{n}{2}\right\rfloor < p < 2\left\lfloor\frac{n}{2}\right\rfloor</math>.
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366641#p366641 Discussion on AoPS/MathLinks]
 
  
 +
Which implies, <math>p< n \le 2p</math>.
 +
 +
As, <math>n-1 \ge p,3,2</math>, there must be a multiple of <math>p</math>, a multiple of <math>3</math> and  a multiple of <math>2</math> in the set, <math>\{m-1,m-2,\cdots,m-n+1\}</math>.
 +
 +
So, <math>2p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)</math> and <math>3p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)</math>.
 +
 +
So, <math>m=2p</math> and <math>m=3p</math> both work for <math>n>5</math>.
 +
 +
So,
 +
 +
There exists solution for all <math>n>3</math>,
 +
 +
Only one Solution for <math>n=4</math>.
 +
 +
Q.E.D.
 +
{{IMO box|num-b=3|num-a=5|year=1981}}
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 09:43, 28 March 2012

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 Solution

Let, for some $n$ and $m$ with $m>n$, $m\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)\ |\ (m-1)(m-2)\cdots(m-n+1)$.

We can trivially check that, there is no such $m$ for $n=3$, only $m=3$ works for $n=4$ and $m=3,8$ works for $n=5$.

Now, consider, $n>5$. By Bertrand's postulate there is a prime $p$ such that $2 \le \left\lfloor\frac{n}{2}\right\rfloor < p < 2\left\lfloor\frac{n}{2}\right\rfloor$.

Which implies, $p< n \le 2p$.

As, $n-1 \ge p,3,2$, there must be a multiple of $p$, a multiple of $3$ and a multiple of $2$ in the set, $\{m-1,m-2,\cdots,m-n+1\}$.

So, $2p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)$ and $3p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)$.

So, $m=2p$ and $m=3p$ both work for $n>5$.

So,

There exists solution for all $n>3$,

Only one Solution for $n=4$.

Q.E.D.

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=45769"