PUMaC 2021 · 团队赛 · 第 10 题
PUMaC 2021 — Team Round — Problem 10
题目详情
- Determine the number of pairs ( a, b ) , where 1 ≤ a ≤ b ≤ 100 are positive integers, so that 3 3 a + b is an integer. 2 2 a + b
解析
- Determine the number of pairs ( a, b ) , where 1 ≤ a ≤ b ≤ 100 are positive integers, so that 3 3 a + b is an integer. 2 2 a + b Proposed by: Frank Lu Answer: 122 Factor a = dx, b = dy, where x, y are relatively prime (so d = gcd( a, b ) . ) Now, substituting 3 3 3 3 x + y a + b 3 3 2 2 these into the equation, we get = d . We now consider x + y and x + y . Notice that 2 2 2 2 a + b x + y 3 2 2 the greatest common divisor of these two expressions is equal to that of y − xy = y ( y − x ) and 2 2 2 2 2 x + y . However, since x, y are relatively prime, y is relatively prime to x + y . Furthermore, 2 2 we see that y − x, x + y have the same gcd as y − x and 2 yx. Therefore, if x − y is odd, we see that these two are relatively prime; otherwise they only share a common factor of 2 . 2 2 x + y 2 2 2 2 Therefore, we see that d must be divisible by if x + y is even, and x + y if this is odd. 2 We can then go through the various cases that we can have for x, y ; notice that both of them must be at most 9 . In running through this list, we need to have y ≥ x, and case work through 2 2 the value of x. Note that x ≤ 6 . In fact, noticing that b must be divisible by y ( x + y ) , we need y ≤ 4 . 2 y ( y +1) 2 For x = 1 , we see that the smallest value of b is y ( y + 1) if y is even and if y is odd, 2 and all values of b are divisible by this smallest value. We thus need y ≤ 5 . y = 1 yields us 100 100 with 100 pairs, y = 2 yields us with = 10 , y = 3 yields us with ⌊ ⌋ = 6 , y = 4 only gives 10 15 one pair, and y = 5 yields us with exactly one pair too. 2 2 For x = 2 , we only have the pair (2 , 3) for ( x, y ) , with the smallest value of b being (3(2 +3 )) = 2 2 3 · 13 = 39 , which only gives us 2 pairs. Finally, for x = 3 , we have the pairs 4(3 + 4 ) = 100 2 2 5(3 +5 ) and = 85 . 2 4 Our total is 100 + 10 + 6 + 1 + 1 + 2 + 2 = 122 .