HMMT 二月 2022 · 冲刺赛 · 第 15 题

HMMT February 2022 — Guts Round — Problem 15

[9] Let N be the number of triples of positive integers ( a, b, c ) satisfying 2020 a ≤ b ≤ c, gcd( a, b, c ) = 1 , abc = 6 . Compute the remainder when N is divided by 1000.

解析

[9] Let N be the number of triples of positive integers ( a, b, c ) satisfying 2020 a ≤ b ≤ c, gcd( a, b, c ) = 1 , abc = 6 . Compute the remainder when N is divided by 1000. Proposed by: Benjamin Wu Answer: 602 p q p q p q 1 1 2 2 3 3 Solution: Let n = 2020. If we let a = 2 · 3 , b = 2 · 3 , c = 2 · 3 , then the number of ordered triples ( a, b, c ) that satisfy the second and third conditions is the number of nonnegative solutions to p + p + p = n and q + q + q = n , where at least one of p , p , p is zero and at least one of q , q , q 1 2 3 1 2 3 1 2 3 1 2 3 is zero (otherwise, gcd( a, b, c ) > 1). By complementary counting, the number is 2 n + 2 n − 1 2 − = 9 n . 2 2 Let ℓ be the number of unordered triples ( a, b, c ) with a, b, c distinct, and m the number of unordered 2 triples ( a, b, c ) with two numbers equal. Since it is impossible for a = b = c , we have 9 n = 6 ℓ + 3 m . We now count m . Without loss of generality, assume a = b . For the factors of 2, we have two choices: 2020 1010 either assign 2 to c or assign 2 to both a and b . We have a similar two choices for the factors of 3. Therefore m = 4. Our final answer is 2 6 ℓ + 3 m + 3 m 9 · 2020 + 12 2 N = m + n = = = 2 + 6 · 1010 ≡ 602 (mod 1000) . 6 6