返回题库

HMMT 十一月 2017 · GEN 赛 · 第 3 题

HMMT November 2017 — GEN Round — Problem 3

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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.
解析

英文解析

  1. 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.