HMMT 十一月 2024 · 冲刺赛 · 第 27 题
HMMT November 2024 — Guts Round — Problem 27
题目详情
- [13] For any positive integer n , let f ( n ) be the number of ordered triples ( a, b, c ) of positive integers such that • max( a, b, c ) divides n and • gcd( a, b, c ) = 1 . Compute f (1) + f (2) + · · · + f (100) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2024, November 09, 2024 — GUTS ROUND Organization Team Team ID#
解析
- [13] For any positive integer n , let f ( n ) be the number of ordered triples ( a, b, c ) of positive integers such that • max( a, b, c ) divides n and • gcd( a, b, c ) = 1. Compute f (1) + f (2) + · · · + f (100). Proposed by: Pitchayut Saengrungkongka Answer: 1000000 P n 3 Solution: We will show that f ( m ) = n . Indeed, consider the map m =1 3 4 g : { 1 , . . . , n } → { 1 , . . . , n } a b c g ( a, b, c ) = , , , max( a, b, c ) . gcd( a,b,c ) gcd( a,b,c ) gcd( a,b,c ) 3 We claim that g is a bijection between { 1 , . . . , n } and tuples ( a, b, c, m ) that satisfy m ≤ n , max( a, b, c ) | m , a b c and gcd( a, b, c ) = 1. Note that g ( a, b, c ) always satisfies these properties because gcd , , = gcd( a,b,c ) gcd( a,b,c ) gcd( a,b,c ) gcd( a,b,c ) = 1 and gcd( a,b,c ) max( a,b,c ) a b c max , , = gcd( a,b,c ) gcd( a,b,c ) gcd( a,b,c ) gcd( a,b,c ) divides max( a, b, c ). It remains to show g is both injective and surjective. Injectivity. Suppose that g ( a , b , c ) = g ( a , b , c ). Then, 1 1 1 2 2 2 a b c gcd( a , b , c ) 1 1 1 1 1 1 = = = . a b c gcd( a , b , c ) 2 2 2 2 2 2 Without loss of generality, assume a ≥ b ≥ c , which implies a ≥ b ≥ c . Then, 1 1 1 2 2 2 a = max( a , b , c ) = max( a , b , c ) = a , 1 1 1 1 2 2 2 2 so b = b and c = c as well. Thus, g is injective. 1 2 1 2 4 Surjectivity. Now suppose we have a tuple ( a, b, c, m ) ∈ { 1 , . . . , n } satisfying max( a, b, c ) | m and m gcd( a, b, c ) = 1. Let d = . Then, gcd( da, db, dc ) = d and max( da, db, dc ) = d · max( a, b, c ) = max( a,b,c ) m ≤ n , so da db dc g ( da, db, dc ) = , , , max( da, db, dc ) = ( a, b, c, m ) . d d d Hence, g is surjective. 3 We conclude g is a bijection between { 1 , . . . , n } and tuples ( a, b, c, m ) satisfying max( a, b, c ) | m and gcd( a, b, c ) = 1. We have f ( m ) such tuples for each m by definition, so n X 3 3 f ( m ) = { 1 , . . . , n } = n . m =1 3 Thus, f (1) + · · · + f (100) = 100 = 1000000 .