1986 USAMO Problems/Problem 1

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

[b](a)[/b] 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](b)[/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.

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

Page

Toolbox

Search

1986 USAMO Problems/Problem 1

Problem

Solution

See Also