HMMT 十一月 2022 · 冲刺赛 · 第 22 题
HMMT November 2022 — Guts Round — Problem 22
题目详情
- [12] Find the number of pairs of integers ( a, b ) with 1 ≤ a < b ≤ 57 such that a has a smaller remainder 2 than b when divided by 57 .
解析
- [12] Find the number of pairs of integers ( a, b ) with 1 ≤ a < b ≤ 57 such that a has a smaller 2 remainder than b when divided by 57 . Proposed by: Zixiang Zhou Answer: 738 Solution: There are no such pairs when b = 57, so we may only consider pairs with 1 ≤ a < b ≤ 56. 2 2 The key idea is that unless a mod 57 = b mod 57, ( a, b ) can be paired with (57 − b, 57 − a ) and 2 2 exactly one of them satisfies a mod 57 < b mod 57. Hence if X is the number of pairs ( a, b ) with 2 2 1 ≤ a < b ≤ 56 and a ≡ b (mod 57), then the answer is 1 56 − X . 2 2 2 2 To count X , let’s first count the number of pairs ( a, b ) with 1 ≤ a, b ≤ 57 and a ≡ b (mod 57). By the Chinese Remainder Theorem, the condition is equivalent to ( a − b )( a + b ) ≡ 0 (mod 3) and ( a − b )( a + b ) ≡ 0 (mod 19). There are 2 · 3 − 1 = 5 pairs of residues modulo 3 where ( a − b )( a + b ) ≡ 0 (mod 3), namely (0 , 0) , (1 , 1) , (2 , 2) , (1 , 2) , (2 , 1). Similarly, there are 2 · 19 − 1 = 37 pairs of residues modulo 19 where ( a − b )( a + b ) ≡ 0 (mod 19). By the Chinese Remainder Theorem, each choice of residues modulo 3 for a and b and residues modulo 19 for a and b corresponds to unique residues modulo 57 for a and b . It follows that there are 5 · 37 = 185 such pairs. To get the value of X , we need to subtract the 57 pairs where a = b and divide by 2 for the pairs with a > b , for a value of 1 X = (185 − 57) = 64. 2 Therefore the final answer is 1 56 − 64 = 738 . 2 2