PUMaC 2020 · 组合（A 组） · 第 8 题
PUMaC 2020 — Combinatorics (Division A) — Problem 8
题目详情
- Let f ( k ) denote the number of triples ( a, b, c ) of positive integers satisfying a + b + c = 2020 with ( k − 1) not dividing a , k not dividing b , and ( k + 1) not dividing c . Find the product of all integers k in the range 3 ≤ k ≤ 20 such that ( k + 1) divides f ( k ). 2
解析
- Let f ( k ) denote the number of triples ( a, b, c ) of positive integers satisfying a + b + c = 2020 with ( k − 1) not dividing a , k not dividing b , and ( k + 1) not dividing c . Find the product of all integers k in the range 3 ≤ k ≤ 20 such that ( k + 1) divides f ( k ). Proposed by Sunay Joshi Answer: 360 . Solution: Let m = 2020, for convenience. We use generating functions. The generating function for a is k − 1 k − 2 1 1 x − x x (1 − x ) − = = . k − 1 k − 1 k − 1 1 − x 1 − x (1 − x )(1 − x ) (1 − x )(1 − x ) k − 1 k x (1 − x ) x (1 − x ) Similarly, the generating functions for b and c are and , respectively. k k +1 (1 − x )(1 − x ) (1 − x )(1 − x ) 3 k +1 x − x Thus, the generating function for a + b + c is . 3 k +1 (1 − x ) (1 − x ) m We must find the coefficient of x in this generating function. By adding and subtracting 1 to the numerator, we can rewrite this as 3 k +1 2 ( x − 1) + (1 − x ) − ( x + x + 1) 1 = + . 3 k +1 2 k +1 3 (1 − x ) (1 − x ) (1 − x ) (1 − x ) (1 − x ) 5 ( ) 2 − ( x + x +1) m +2 1 m m The coefficient of x in is . To find the coefficient of x in , we 3 2 k +1 (1 − x ) 2 (1 − x ) (1 − x ) 1 n n note that the coefficient of x in is the coefficient of x in the expansion 2 k +1 (1 − x ) (1 − x ) 2 k +1 2( k +1) (1 + 2 x + 3 x + . . . )(1 + x + x + . . . ) , i.e. t ( n,k ) ∑ ( n + 1 − t ( k + 1)) , t =0 n +1 n where t ( n, k ) = b c . Expanding this out, we find that the coefficient of x is k +1 t ( n, k )( t ( n, k ) + 1) c = ( n + 1)( t ( n, k ) + 1) − ( k + 1) . n 2 2 − ( x + x +1) m Since we are looking for the coefficient of x in , we want − ( c + c + c ). 2 k +1 m m − 1 m − 2 (1 − x ) (1 − x ) m Putting this all together, the coefficient of x (i.e. f ( k )) in our original generating function is given as f ( k ) = ( ) m + 2 t ( m, k )( t ( m, k ) + 1) − (( m + 1)( t ( m, k ) + 1) − ( k + 1)) 2 2 t ( m − 1 , k )( t ( m − 1 , k ) + 1) − (( m )( t ( m − 1 , k ) + 1) − ( k + 1)) 2 t ( m − 2 , k )( t ( m − 2 , k ) + 1) − (( m − 1)( t ( m − 2 , k ) + 1) − ( k + 1)) . 2 Recall that we are only looking at f ( k ) (mod k + 1). Since t ( · , · ) is always an integer, the second terms in the parentheses are divisible by ( k + 1), and we find ( ) m + 2 f ( k ) ≡ − ( m + 1)( t ( m, k ) + 1) − ( m )( t ( m − 1 , k ) + 1) − ( m − 1)( t ( m − 2 , k ) + 1) 2 ( ) m − 1 ≡ − (( m + 1) t ( m, k ) + ( m ) t ( m − 1 , k ) + ( m − 1) t ( m − 2 , k )) (mod k + 1) . 2 It remains to check which k ∈ [3 , 20] make the right hand side equal 0, i.e. when ( ) ( ⌊ ⌋ ⌊ ⌋ ⌊ ⌋) m − 1 m + 1 m m − 1 − ( m + 1) + ( m ) + ( m − 1) ≡ 0 (mod k + 1) . 2 k + 1 k + 1 k + 1 A quick computation shows the only possible k are 4, 9, and 10, hence the answer is 360. 6