HMMT 十一月 2020 · 团队赛 · 第 5 题
HMMT November 2020 — Team Round — Problem 5
题目详情
- [40] For each positive integer n , let a be the smallest nonnegative integer such that there is only one n positive integer at most n that is relatively prime to all of n, n + 1 , . . . , n + a . If n < 100, compute n the largest possible value of n − a . n
解析
- [40] For each positive integer n , let a be the smallest nonnegative integer such that there is only one n positive integer at most n that is relatively prime to all of n, n + 1 , . . . , n + a . If n < 100, compute n the largest possible value of n − a . n Proposed by: Hahn Lheem Answer: 16 Solution: Note that 1 is relatively prime to all positive integers. Therefore, the definition of a can n equivalently be stated as: “ a is the smallest nonnegative integer such that for all integers x , 2 ≤ x ≤ n , n x shares a prime factor with at least one of n, n + 1 , . . . n + a .” n The condition is equivalent the statement that the integers from n to n + a must include multiples of n all primes less than n . Therefore, if p is the largest prime satisfying p < n , then n + a ≥ 2 p . n We now claim that a = 2 p − n works for all n > 11. For all primes q at most a + 1, it is apparent n n that n, n + 1 , . . . , n + a indeed contains a multiple of q . For primes a + 1 < q ≤ p , we then find that n n 2 q ≤ n + a . To finish, we claim that 2 q ≥ n , which would be implied by 2( a + 2) ≥ n ⇐⇒ p ≥ n n 3 n/ 4 − 1. This is indeed true for all 11 < n < 100. We therefore wish to maximize n − a = n − (2 p − n ) = 2( n − p ). Therefore, the answer is twice the n largest difference between two primes less than 100. This difference is 8 (from 89 to 97), so the answer is 16. Since this is greater than 11, we have not lost anything by ignoring the smaller cases.