PUMaC 2023 · 团队赛 · 第 3 题
PUMaC 2023 — Team Round — Problem 3
题目详情
- A quadratic polynomial f ( x ) is called sparse if its degree is exactly 2, if it has integer coeffi- cients, and if there exists a nonzero polynomial g ( x ) with integer coefficients such that f ( x ) g ( x ) has degree at most 3 and f ( x ) g ( x ) has at most two nonzero coefficients. Find the number of sparse quadratics whose coefficients lie between 0 and 10, inclusive. 1515 1975
解析
- A quadratic polynomial f ( x ) is called sparse if its degree is exactly 2, if it has integer coeffi- cients, and if there exists a nonzero polynomial g ( x ) with integer coefficients such that f ( x ) g ( x ) has degree at most 3 and f ( x ) g ( x ) has at most two nonzero coefficients. Find the number of sparse quadratics whose coefficients lie between 0 and 10, inclusive. Proposed by Sunay Joshi 1 Answer: 228 Let N = 10. d 2 If f ( x ) g ( x ) has exactly one nonzero coefficient, then f ( x ) g ( x ) = cx . Thus f ( x ) = ax for 1 ≤ a ≤ N , yielding N = 10 quadratics. If f ( x ) g ( x ) has exactly two nonzero coefficients, we proceed by casework on the degree of f ( x ) g ( x ). Each case considers the smallest possible degree of f ( x ) g ( x ) to ensure that the cases are distinct. 2 2 If the degree of f ( x ) g ( x ) is 2, then f ( x ) = ax + bx or f ( x ) = ax + c for a, b, c ̸ = 0. This 2 yields 2 N = 200 quadratics. 2 2 2 If the degree of f ( x ) g ( x ) is 3, we claim that f ( x ) = km x + kmnx + kn for k, m, n ∈ Z , 3 2 gcd( m, n ) = 1. To see this, suppose f ( x ) g ( x ) = ax + b = ( cx + dx + e )( ℓx + p ). Dividing 3 2 through by a = cℓ , it suffices to consider x + b = ( x + dx + e )( x + p ) over the rationals. 2 Expanding, we find p + d = 0, dp + e = 0, and b = ep . This implies p = − d , e = d , and 3 3 3 3 3 b = − d . Thus ax + b must be of the form km x + kn with gcd( m, n ) = 1, and the claim follows. 2 2 In this case, note that km ≤ N and kn ≤ N implies kmn ≤ N . We proceed by casework on k . 2 2 If k = 1, then m , n ≤ 10, hence m, n ∈ { 1 , 2 , 3 } . All pairs excluding m = n ∈ { 2 , 3 } are 2 2 2 coprime, so we find 3 − 2 = 7 solutions. If k = 2, then m , n ≤ 5, hence m, n ∈ { 1 , 2 } . All 2 pairs excluding m = n = 2 are coprime, so we find 2 − 1 = 3 solutions. If 3 ≤ k ≤ 10, then 2 2 m , n ≤ 1, hence m = n = 1. This yields 1 solution for each value of k , hence 8 in total. Thus this case yields 7 + 3 + 8 = 18 solutions. Adding up, we find a total of 10 + 200 + 18 = 228 solutions. 1515 1975