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 "1986 USAMO Problems/Problem 1"

(Created page with "==Problem== <math>(\text{a})</math> Do there exist 14 consecutive positive integers each of which is divisible by one or more primes <math>p</math> from the interval <math>2\le p...")
 
m (→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
−
To solve part (a), we first note that for any 14 consecutive positive integers, exactly 7 are even (divisible by 2) and therefore satisfy the criteria. We can remove these from the problem, and simplify it to the following question, which is equivalent to part (a):
+
(a)    To solve part (a), we first note that for any 14 consecutive positive integers, exactly 7 are even (divisible by 2) and therefore satisfy the criteria. We can remove these from the problem, and simplify it to the following question, which is equivalent to part (a):
 
"Do there exist 7 consecutive positive odd integers each of which is divisible by one or more primes <math>p</math> from the interval <math>3\le p \le 11</math>?"
 
"Do there exist 7 consecutive positive odd integers each of which is divisible by one or more primes <math>p</math> from the interval <math>3\le p \le 11</math>?"
 
Among any 7 consecutive positive odd integers, the following holds:
 
Among any 7 consecutive positive odd integers, the following holds:
Line 14: Line 14:
 
For every one of these seven integers to be divisible by one of 3, 5, 7, or 11, there must be 3 multiples of 3, 2 multiples of 5, 1 multiple of 7, and 1 multiple of 11. Additionally, none of these integers may be a multiple of any two of the four aforementioned primes. Otherwise, the Pigeonhole Principle dictates that at least one integer is not divisible by any of the four, thus failing to meet the criteria. But this cannot be. Calling the consecutive odd integers <math>a_1, a_2, \dots, a_7</math>, we note that <math>a_1</math>, <math>a_4</math>, and <math>a_7</math> must be multiples of 3, and therefore cannot be multiples of 5, 7, or 11. But for there to be two multiples of 5, they must be one of the two pairs <math>(a_1,a_6)</math> and <math>(a_2,a_7)</math>. But each of these pairs contains a multiple of 3, and so at least one of the 7 odd integers is divisible by none of the primes 3, 5, 7, or 11. Therefore the answer to part (a) is no.
 
For every one of these seven integers to be divisible by one of 3, 5, 7, or 11, there must be 3 multiples of 3, 2 multiples of 5, 1 multiple of 7, and 1 multiple of 11. Additionally, none of these integers may be a multiple of any two of the four aforementioned primes. Otherwise, the Pigeonhole Principle dictates that at least one integer is not divisible by any of the four, thus failing to meet the criteria. But this cannot be. Calling the consecutive odd integers <math>a_1, a_2, \dots, a_7</math>, we note that <math>a_1</math>, <math>a_4</math>, and <math>a_7</math> must be multiples of 3, and therefore cannot be multiples of 5, 7, or 11. But for there to be two multiples of 5, they must be one of the two pairs <math>(a_1,a_6)</math> and <math>(a_2,a_7)</math>. But each of these pairs contains a multiple of 3, and so at least one of the 7 odd integers is divisible by none of the primes 3, 5, 7, or 11. Therefore the answer to part (a) is no.
  
−
To solve part (b), we use a strategy similar to the one used in part (a), reducing part (b) to this equivalent question:
+
(b)    To solve part (b), we use a strategy similar to the one used in part (a), reducing part (b) to this equivalent question:
 
"Do there exist 10 consecutive positive odd integers each of which is divisible by one or more primes <math>p</math> from the interval <math>3\le p \le 13</math>?"
 
"Do there exist 10 consecutive positive odd integers each of which is divisible by one or more primes <math>p</math> from the interval <math>3\le p \le 13</math>?"
 
(We will ignore the case where the first of the 21 integers is odd, resulting in 11 odd integers instead of 10, as it is only true if the weaker, 10-integer argument is also true.)
 
(We will ignore the case where the first of the 21 integers is odd, resulting in 11 odd integers instead of 10, as it is only true if the weaker, 10-integer argument is also true.)
Line 25: Line 25:
 
For every one of these ten integers to be divisible by one of 3, 5, 7, 11, or 13, there must be 4 multiples of 3, 2 multiples of 5, 2 multiples of 7, 1 multiple of 11, and 1 multiple of 13. As before, none of these integers may be a multiple of any two of the five primes. Calling the consecutive odd integers <math>a_1, a_2, \dots, a_{10}</math>, we note that <math>a_1</math>, <math>a_4</math>, <math>a_7</math>, and <math>a_{10}</math> must be multiples of 3, and therefore cannot be multiples of 5, 7, 11, or 13. Unlike part (a), however, this stipulation is not a dead end. Let the multiples of 5 be <math>a_3</math> and <math>a_8</math> and let the multiples of 7 be <math>a_2</math> and <math>a_9</math>. The multiples of 11 and 13 are <math>a_5</math> and <math>a_6</math>, in some order (it doesn't really matter which). An example of a sequence of 21 consecutive positive integers satisfying part (b) is the integers from 9440 to 9460 (inclusive), which can be obtained by solving modular equations that result from these statements. So the answer to part (b) is yes.
 
For every one of these ten integers to be divisible by one of 3, 5, 7, 11, or 13, there must be 4 multiples of 3, 2 multiples of 5, 2 multiples of 7, 1 multiple of 11, and 1 multiple of 13. As before, none of these integers may be a multiple of any two of the five primes. Calling the consecutive odd integers <math>a_1, a_2, \dots, a_{10}</math>, we note that <math>a_1</math>, <math>a_4</math>, <math>a_7</math>, and <math>a_{10}</math> must be multiples of 3, and therefore cannot be multiples of 5, 7, 11, or 13. Unlike part (a), however, this stipulation is not a dead end. Let the multiples of 5 be <math>a_3</math> and <math>a_8</math> and let the multiples of 7 be <math>a_2</math> and <math>a_9</math>. The multiples of 11 and 13 are <math>a_5</math> and <math>a_6</math>, in some order (it doesn't really matter which). An example of a sequence of 21 consecutive positive integers satisfying part (b) is the integers from 9440 to 9460 (inclusive), which can be obtained by solving modular equations that result from these statements. So the answer to part (b) is yes.
  
 +
==See Also==
  
−
 
+
{{USAMO box|year=1986|before=First<br>Problem|num-a=2}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 15:49, 20 August 2016

Problem

$(\text{a})$ Do there exist 14 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 11$?

$(\text{b})$ Do there exist 21 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 13$?

Solution

(a) To solve part (a), we first note that for any 14 consecutive positive integers, exactly 7 are even (divisible by 2) and therefore satisfy the criteria. We can remove these from the problem, and simplify it to the following question, which is equivalent to part (a): "Do there exist 7 consecutive positive odd integers each of which is divisible by one or more primes $p$ from the interval $3\le p \le 11$?" Among any 7 consecutive positive odd integers, the following holds: \[\text{Either 2 or 3 are divisible by 3}\] \[\text{Either 1 or 2 are divisible by 5}\] \[\text{Exactly 1 is divisible by 7}\] \[\text{Either 0 or 1 are divisible by 11}\] For every one of these seven integers to be divisible by one of 3, 5, 7, or 11, there must be 3 multiples of 3, 2 multiples of 5, 1 multiple of 7, and 1 multiple of 11. Additionally, none of these integers may be a multiple of any two of the four aforementioned primes. Otherwise, the Pigeonhole Principle dictates that at least one integer is not divisible by any of the four, thus failing to meet the criteria. But this cannot be. Calling the consecutive odd integers $a_1, a_2, \dots, a_7$, we note that $a_1$, $a_4$, and $a_7$ must be multiples of 3, and therefore cannot be multiples of 5, 7, or 11. But for there to be two multiples of 5, they must be one of the two pairs $(a_1,a_6)$ and $(a_2,a_7)$. But each of these pairs contains a multiple of 3, and so at least one of the 7 odd integers is divisible by none of the primes 3, 5, 7, or 11. Therefore the answer to part (a) is no.

(b) To solve part (b), we use a strategy similar to the one used in part (a), reducing part (b) to this equivalent question: "Do there exist 10 consecutive positive odd integers each of which is divisible by one or more primes $p$ from the interval $3\le p \le 13$?" (We will ignore the case where the first of the 21 integers is odd, resulting in 11 odd integers instead of 10, as it is only true if the weaker, 10-integer argument is also true.) Among any 10 consecutive positive odd integers, the following holds: \[\text{Either 3 or 4 are divisible by 3}\] \[\text{Exactly 2 are divisible by 5}\] \[\text{Either 1 or 2 are divisible by 7}\] \[\text{Either 0 or 1 are divisible by 11}\] \[\text{Either 0 or 1 are divisible by 13}\] For every one of these ten integers to be divisible by one of 3, 5, 7, 11, or 13, there must be 4 multiples of 3, 2 multiples of 5, 2 multiples of 7, 1 multiple of 11, and 1 multiple of 13. As before, none of these integers may be a multiple of any two of the five primes. Calling the consecutive odd integers $a_1, a_2, \dots, a_{10}$, we note that $a_1$, $a_4$, $a_7$, and $a_{10}$ must be multiples of 3, and therefore cannot be multiples of 5, 7, 11, or 13. Unlike part (a), however, this stipulation is not a dead end. Let the multiples of 5 be $a_3$ and $a_8$ and let the multiples of 7 be $a_2$ and $a_9$. The multiples of 11 and 13 are $a_5$ and $a_6$, in some order (it doesn't really matter which). An example of a sequence of 21 consecutive positive integers satisfying part (b) is the integers from 9440 to 9460 (inclusive), which can be obtained by solving modular equations that result from these statements. So the answer to part (b) is yes.

See Also

1986 USAMO (Problems • Resources)
Preceded by
First
Problem 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_USAMO_Problems/Problem_1&oldid=80042"