HMMT 二月 2023 · ALGNT 赛 · 第 8 题
HMMT February 2023 — ALGNT Round — Problem 8
题目详情
- Let S be the set of ordered pairs ( a, b ) of positive integers such that gcd( a, b ) = 1. Compute ⌊ ⌋ ∑ 300 . 2 a + 3 b ( a,b ) ∈ S
解析
- Let S be the set of ordered pairs ( a, b ) of positive integers such that gcd( a, b ) = 1. Compute ⌊ ⌋ ∑ 300 . 2 a + 3 b ( a,b ) ∈ S Proposed by: Pitchayut Saengrungkongka Answer: 7400 Solution: The key claim is the following. Claim: The sum in the problem is equal to the number of solutions of 2 x + 3 y ≤ 300 where x, y are positive integers. Proof. The sum in the problem is the same as counting the number of triples ( a, b, d ) of positive integers such that gcd( a, b ) = 1 and d (2 a + 3 b ) ≤ 300. Now, given such ( a, b, d ), we biject it to the pair ( x, y ) described in the claim by x = da and x = db . This transformation can be reversed by d = gcd( x, y ), a = x/d , and b = y/d , implying that it is indeed a bijection, so the sum is indeed equal to the number of such ( x, y ). Hence, we wish to count the number of positive integer solutions to 2 x + 3 y ≤ 300. One way to do this is via casework on y , which we know to be an integer less than 100: 300 − 6 k • If y is even, then y = 2 k for 1 ≤ k ≤ 49. Fixing k , there are exactly = 150 − 3 k values of 2 x which satisfy the inequality, hence the number of solutions in this case is 49 ∑ 150 · 49 (150 − 3 k ) = = 3675 . 2 k =1 302 − 6 k • If y is odd, then y = 2 k − 1 for 1 ≤ k ≤ 50. Fixing y , there are exactly = 151 − 3 k values 2 of x which satisfy the inequality, hence the number of solutions in this case is 50 ∑ 149 · 50 (151 − 3 k ) = = 3725 . 2 k =1 The final answer is 3675 + 3725 = 7400.