Maths Olympiad Prep

Library / /14 of 115

Number theory Difficulty 6.6 National olympiad Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

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 pp from the interval 3p113\le p \le 11 ?"
Among any 7 consecutive positive odd integers, the following holds: Either 2 or 3 are divisible by 3\text{Either 2 or 3 are divisible by 3} Either 1 or 2 are divisible by 5\text{Either 1 or 2 are divisible by 5} Exactly 1 is divisible by 7\text{Exactly 1 is divisible by 7} Either 0 or 1 are divisible by 11\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 a1,a2,,a7a_1, a_2, \dots, a_7 , we note that a1a_1 , a4a_4 , and a7a_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 (a1,a6)(a_1,a_6) and (a2,a7)(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 pp from the interval 3p133\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: Either 3 or 4 are divisible by 3\text{Either 3 or 4 are divisible by 3} Exactly 2 are divisible by 5\text{Exactly 2 are divisible by 5} Either 1 or 2 are divisible by 7\text{Either 1 or 2 are divisible by 7} Either 0 or 1 are divisible by 11\text{Either 0 or 1 are divisible by 11} Either 0 or 1 are divisible by 13\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 a1,a2,,a10a_1, a_2, \dots, a_{10} , we note that a1a_1 , a4a_4 , a7a_7 , and a10a_{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 a3a_3 and a8a_8 and let the multiples of 7 be a2a_2 and a9a_9 . The multiples of 11 and 13 are a5a_5 and a6a_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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.