Difference between revisions of "1981 IMO Problems/Problem 4"
m |
(template) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | (a) For which values of <math> | + | (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> | + | (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> | + | 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> | + | 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}} | ||
− | == | + | {{IMO box|num-b=3|num-a=5|year=1981}} |
− | |||
− | |||
− | |||
− | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 20:46, 25 October 2007
Problem
(a) For which values of is there a set of
consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining
numbers?
(b) For which values of is there exactly one set having the stated property?
Solution
Let be the greatest element of the set, written in its prime factorization. Then
divides the least common multiple of the other elements of the set if and only if the set has cardinality at least
, since for any of the
, we must go down at least to
to obtain another multiple of
. 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 , we may let
, since all the
must clearly be less than
and this product must also be greater than
if
is at least 4. For
, we may also let
, for the same reasons. However, for
, this does not work, and indeed no set works other than
. 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 |