HMMT 二月 2024 · ALGNT 赛 · 第 7 题
HMMT February 2024 — ALGNT Round — Problem 7
题目详情
- Let P ( n ) = ( n − 1 )( n − 2 ) . . . ( n − 40 ) for positive integers n . Suppose that d is the largest positive integer that divides P ( n ) for every integer n > 2023 . If d is a product of m (not necessarily distinct) prime numbers, compute m . 2 π 2 π
解析
- Let P ( n ) = ( n − 1 )( n − 2 ) . . . ( n − 40 ) for positive integers n . Suppose that d is the largest positive integer that divides P ( n ) for every integer n > 2023. If d is a product of m (not necessarily distinct) prime numbers, compute m . Proposed by: Nithid Anchaleenukoon Answer: 48 Solution: We first investigate what primes divide d . Notice that a prime p divides P ( n ) for all 3 3 3 n ≥ 2024 if and only if { 1 , 2 , . . . , 40 } contains all residues in modulo p . Hence, p ≤ 40. Moreover, 3 x ≡ 1 must not have other solution in modulo p than 1, so p 6 ≡ 1 (mod 3). Thus, the set of prime divisors of d is S = { 2 , 3 , 5 , 11 , 17 , 23 , 29 } . Next, the main claim is that for all prime p ∈ S , the minimum value of ν ( P ( n )) across all n ≥ 2024 p ⌊ ⌋ 40 is . To see why, note the following: p ⌊ ⌋ 40 3 3 3 • Lower Bound. Note that for all n ∈ Z , one can group n − 1 , n − 2 , . . . , n − 40 into p 3 contiguous blocks of size p . Since p 6 ≡ 1 (mod 3), x span through all residues modulo p , so each 3 3 3 block will have one number divisible by p . Hence, among n − 1 , n − 2 , . . . , n − 40 , at least ⌊ ⌋ ⌊ ⌋ 40 40 are divisible by p , implying that ν ( P ( n )) > . p p p 3 3 • Upper Bound. We pick any n such that ν ( n ) = 1 so that only terms in form n − p , n − (2 p ) , p 2 . . . are divisible by p . Note that these terms are not divisible by p either, so in this case, we ⌊ ⌋ 40 have ν ( P ( n )) = . p p ⌊ ⌋ 40 Hence, ν ( d ) = for all prime p ∈ S . Thus, the answer is p p ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ∑ 40 40 40 40 40 40 40 40 = + + + + + + = 48 . p 2 3 5 11 17 23 29 p ∈ S 2 π 2 π