返回题库

HMMT 二月 2019 · 团队赛 · 第 4 题

HMMT February 2019 — Team Round — Problem 4

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

题目详情

英文原题

  1. [ 35 ] Find all positive integers n for which there do not exist n consecutive composite positive integersless than n !.
解析

英文解析

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