HMMT 二月 2019 · 团队赛 · 第 4 题
HMMT February 2019 — Team Round — Problem 4
题目详情
- [ 35 ] Find all positive integers n for which there do not exist n consecutive composite positive integers less than n !.
解析
- [ 35 ] Find all positive integers n for which there do not exist n consecutive composite positive integers less than n !. Proposed by: Brian Reinhart Answer: 1 , 2 , 3 , 4 Solution 1. First, note that clearly there are no composite positive integers less than 2!, and no 3 consecutive composite positive integers less than 3!. The only composite integers less than 4! are 4 , 6 , 8 , 9 , 10 , 12 , 14 , 15 , 16 , 18 , 20 , 21 , 22 , and it is easy to see that there are no 4 consecutive composite positive integers among them. Therefore, all n ≤ 4 works. Define M = lcm(1 , 2 , . . . , n + 1). To see that there are no other such positive integers, we first show that for all n ≥ 5, n ! > M . Let k = b log ( n + 1) c . Note that v ( M ) = k , while 2 2 ⌊ ⌋ ( ) ( ) k k ∑ ∑ n + 1 n + 1 n + 1 v (( n + 1)!) = ≥ − 1 = n + 1 − − k ≥ ( n + 1 − 2) − k = n − k − 1 . 2 i i k 2 2 2 i =1 i =1 This means that at least ( n − k − 1) − k = n − 2 k − 1 powers of 2 are lost when going from ( n + 1)! to M . Since M | ( n + 1)!, when n − 2 k − 1 ≥ k + 1 ⇐⇒ n ≥ 3 k + 2, we have ( n + 1)! ( n + 1)! M ≤ ≤ < n ! , k +1 2 2( n + 1) k k as desired. Since n ≥ 2 − 1, we can rule out all k such that 2 ≥ 3 k + 3, which happens when k ≥ 4 or n ≥ 15. Moreover, when k = 3, we may also rule out all n ≥ 3 k + 2 = 11. We thus need only check values of n between 5 and 10: n = 5: n ! = 120 , M = 60; n = 6: n ! = 720 , M = 420; n = 7: n ! = 5040 , M = 840; n ∈ { 8 , 9 , 10 } : n ! ≥ 40320 , M ≤ 27720. In all cases, n ! > M , as desired. To finish, note that M − 2 , M − 3 , . . . , M − ( n + 1) are all composite (divisible by 2 , 3 , . . . , n + 1 respectively), which gives the desired n consecutive numbers. Therefore, all integers n ≥ 5 do not satisfy the problem condition, and we are done. Solution 2. Here is a different way to show that constructions exist for n ≥ 5. Note that when n + 1 is not prime, the numbers n ! − 2 , n ! − 3 , . . . , n ! − ( n + 1) are all composite (the first n − 1 are clearly composite, the last one is composite because n + 1 | n ! and n ! > 2( n + 1)). Otherwise, if n = p − 1 for prime p ≥ 7, then the numbers ( n − 1)! , ( n − 1)! − 1 , ( n − 1)! − 2 , . . . , ( n − 1)! − ( n − 1) are all composite (the first one and the last n − 2 are clearly composite since ( n − 1)! > 2( n − 1), the second one is composite since p | ( p − 2)! − 1 = ( n − 1)! − 1 by Wilson’s theorem).