PUMaC 2022 · 团队赛 · 第 8 题
PUMaC 2022 — Team Round — Problem 8
题目详情
- Ryan Alweiss storms into the Fine Hall common room with a gigantic eraser and erases all t n − 3 integers n in the interval [2 , 728] such that 3 doesn’t divide n !, where t = ⌈ ⌉ . 2 Find the sum of the leftover integers in that interval modulo 1000. 3 2
解析
- Ryan Alweiss storms into the Fine Hall common room with a gigantic eraser and erases all n − 3 t integers n in the interval [2 , 728] such that 3 doesn’t divide n !, where t = ⌈ ⌉ . 2 Find the sum of the leftover integers in that interval modulo 1000. Proposed by Sunay Joshi Answer: 11 k t 1 2 We claim that the sum of the integers n in the interval [2 , 3 − 1] satisfying 3 | n ! is ( k + 2 k 3 − 1 t 5 k ) · − 1. To see this, first consider the condition 3 | n !. The highest power of a prime 2 n − s ( n ) p p dividing n ! is precisely ν ( n ) = , where s ( n ) denotes the sum of the digits of n in p p p − 1 4 n − s ( n ) n − 3 3 base p . Therefore t ≤ ν ( n ) is equivalent to ⌈ ⌉ ≤ . We split into two cases based 3 2 2 n − s ( n ) n − 3 3 on the parity of n . For n odd, this is ≤ , i.e. s ( n ) ≤ 3. For n even, this is 3 2 2 n − s ( n ) n − 2 3 ≤ , i.e. s ( n ) ≤ 2. In the former case, it follows that the ternary representation 3 2 2 of n must consist of either (a) one 1, (b) one 2 and one 1, or (c) three 1s. In the latter case, the ternary representation of n must consist of (d) one 2 or (e) two 1s. We now count the contribution of a given digit in the five subcases (a) through (e), where we include n = 1 among the valid numbers for convenience. (We will subtract n = 1 at the end.) One can see that the k − 1 contribution is 1 for (a), 2( k − 1)+( k − 1) = 3( k − 1) for (b), for (c), 2 for (d), and ( k − 1) for 2 k − 1 1 j 2 (e). Thus each digit 3 (0 ≤ j ≤ k − 1) contributes 1+3( k − 1)+ +2+( k − 1) = ( k +5 k ) 2 2 k 1 2 3 − 1 times its value, yielding an answer of ( k + 5 k ) · − 1, where we subtract one because we 2 2 must ignore n = 1. Plugging in k = 6, we find a total of 12011 ≡ 11 (mod 1000), our answer. 3 2