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 integersless than n !.
解析
英文解析
- [ 35 ] Find all positive integers n for which there do not exist n consecutive composite positive integersless 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 showthat for all n ≥ 5, n ! > M . Let k = b log ( n + 1) c . Note that v ( M ) = k , while
⌊ ⌋ ( ) ( )22
k k
∑ ∑
n + 1 n + 1 n + 1
v (( n + 1)!) = ≥ − 1 = n + 1 − − k ≥ ( n + 1 − 2) − k = n − k − 1 .
i i k 2
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 kas 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 notsatisfy 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 clearlycomposite, 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 allcomposite (the first one and the last n − 2 are clearly composite since ( n − 1)! > 2( n − 1), the secondone is composite since p | ( p − 2)! − 1 = ( n − 1)! − 1 by Wilson’s theorem).