HMMT 二月 2019 · ALGNT 赛 · 第 6 题
HMMT February 2019 — ALGNT Round — Problem 6
题目详情
- For positive reals p and q , define the remainder when p is divided by q as the smallest nonnegative p − r real r such that is an integer. For an ordered pair ( a, b ) of positive integers, let r and r be the 1 2 q √ √ √ √ remainder when a 2 + b 3 is divided by 2 and 3 respectively. Find the number of pairs ( a, b ) such √ that a, b ≤ 20 and r + r = 2. 1 2
解析
- For positive reals p and q , define the remainder when p is divided by q as the smallest nonnegative p − r real r such that is an integer. For an ordered pair ( a, b ) of positive integers, let r and r be the 1 2 q √ √ √ √ remainder when a 2 + b 3 is divided by 2 and 3 respectively. Find the number of pairs ( a, b ) such √ that a, b ≤ 20 and r + r = 2. 1 2 Proposed by: Yuan Yao Answer: 16 √ √ √ The remainder when we divide a 2 + b 3 by 2 is defined to be the smallest non-negative real r 1 √ √ √ a 2+ b 3 − r x 1 √ √ such that is integral. As is integral iff x is an integral multiple of 2, it follows that 2 2 √ √ √ √ a 2+ b 3 − r √ r = b 3 − c 2, for some integer c . Furthermore given any real r such that is integral, we 1 2 √ may add or subtract 2 to r and the fraction remains an integer. Thus, the smallest non-negative real √ r such that the fraction is an integer must satisfy 0 ≤ r < 2. 1 1 √ √ √ √ Similarly, we find r = a 2 − d 3 for some integer d and 0 ≤ r < 3. Since r + r = 2, then 2 2 1 2 √ √ √ ( a − c ) 2 + ( b − d ) 3 = 2 ⇐⇒ a − c = 1 and b − d = 0 . Finally, substituting in c = a − 1 and d = b plugging back into our bounds for r and r , we get 1 2 { √ √ √ 0 ≤ b 3 − ( a − 1) 2 < 2 √ √ √ 0 ≤ a 2 − b 3 < 3 or √ √ ( a − 1) 2 ≤ b 3 √ √ b 3 < a 2 √ √ b 3 ≤ a 2 √ √ a 2 < ( b + 1) 3 √ √ √ √ Note that b 3 < a 2 = ⇒ b 3 ≤ a 2 and √ √ √ √ √ √ √ √ ( a − 1) 2 ≤ b 3 = ⇒ a 2 ≤ b 3 + 2 < b 3 + 3 = ( b + 1) 3 so the last two inequalities are redundant. We are left with √ √ √ ( a − 1) 2 ≤ b 3 < a 2 . √ √ [ ) Since the non-negative number line is partitioned by intervals of the form ( a − 1) 2 , a 2 for positive integers a , for any positive integer b , we can find a positive integer a that satisfies the inequalities. As clearly a > b , it remains to find the number of b such that a ≤ 20. This is bounded by √ √ √ √ 20 2 √ b 3 < a 2 ≤ 20 2 ⇐⇒ b < = ⇒ b ≤ 16 3 so there are 16 values of b and thus 16 ordered pairs of positive integers ( a, b ) that satisfy the problem.