HMMT 十一月 2017 · GEN 赛 · 第 3 题
HMMT November 2017 — GEN Round — Problem 3
题目详情
英文原题
- Find the number of integers n with 1 ≤ n ≤ 2017 so that ( n − 2)( n − 0)( n − 1)( n − 7) is an integermultiple of 1001.
解析
英文解析
- Find the number of integers n with 1 ≤ n ≤ 2017 so that ( n − 2)( n − 0)( n − 1)( n − 7) is an integermultiple of 1001.
Proposed by: Dhruv Rohatgi
Answer: 99
Note that 1001 = 7 · 11 · 13, so the stated product must be a multiple of 7, as well as a multiple of
11, as well as a multiple of 13. There are 4 possible residues of n modulo 11 for which the productis a multiple of 11; similarly, there are 4 possible residues of n modulo 13 for which the product is amultiple of 13. However, there are only 3 possible residues of n modulo 7 for which the product is amultiple of 7.
Consider each of these 4 · 4 · 3 = 48 possible triples of remainders. By the Chinese Remainder Theoremthere is exactly one value of n with 1 ≤ n ≤ 1001 achieving those remainders, and exactly one valueof n with 16 ≤ n ≤ 1016 achieving those remainders. Similarly, there is exactly one value of n with
1017 ≤ n ≤ 2017 with those same remainders. Hence there are 96 values of n with 16 ≤ n ≤ 2017 suchthat ( n − 2)( n − 0)( n − 1)( n − 7) is a multiple of 1001.
It remains to check n ∈ { 1 , 2 , 3 , . . . , 15 } . Since the product must be a multiple of 7, we can narrowthe set to { 1 , 2 , 7 , 8 , 9 , 14 } . The first 3 values work trivially, since the product is 0. It can be easilychecked that none of the remaining values of n yield a product which is a multiple of 11. Hence, thefinal answer is 96 + 3 = 99.