HMMT 十一月 2024 · THM 赛 · 第 8 题
HMMT November 2024 — THM Round — Problem 8
题目详情
- For all positive integers r and s , let Top( r, s ) denote the top number (i.e., numerator) when is written s in simplified form. For instance, Top(20 , 24) = 5 . Compute the number of ordered pairs of positive integers ( a, z ) such that 200 ≤ a ≤ 300 and Top( a, z ) = Top( z, a − 1) .
解析
- For all positive integers r and s , let Top( r, s ) denote the top number (i.e., numerator) when is written s in simplified form. For instance, Top(20 , 24) = 5. Compute the number of ordered pairs of positive integers ( a, z ) such that 200 ≤ a ≤ 300 and Top( a, z ) = Top( z, a − 1). Proposed by: David Dong, Derek Liu, Henrick Rabinovitz, Jackson Dryg, Krishna Pothapragada, Linus Yifeng Tang, Pitchayut Saengrungkongka, Srinivas Arun Answer: 38 r Solution: In general, Top( r, s ) = . We characterize all possible ( a, z ) as follows. gcd( r,s ) Claim 1. For any positive integers a and z , we have Top( a, z ) = Top( z, a − 1) if and only if there 2 2 exists positive integers d and e such that e | d − 1, a = d , and z = de . 2 2 d d 2 Proof. ( ⇐ ) From e | d − 1, we deduce that gcd( d, e ) = 1. Thus, Top( a, z ) = = = d . We 2 gcd( d ,de ) d de 2 also have gcd( z, a − 1) = gcd( de, d − 1) = e , so Top( z, a − 1) = = d as well. e ( ⇒ ) Let d = gcd( a, z ) and e = gcd( z, a − 1). We have that gcd( d, e ) = 1 because it divides both a and a/d a z a d a − 1. The equation implies that = , or = . The left side has simplified form , and the right d e z e z/d 2 2 side is already simplified. Thus, a = d and z = de . Finally, e = gcd( z, a − 1) | a − 1 = d − 1. 2 The condition that 200 ≤ a ≤ 300 implies d ∈ { 15 , 16 , 17 } . Once we select d , each divisor e of d − 1 yields a solution. Thus, the answer is 2 2 2 τ (15 − 1) + τ (16 − 1) + τ (17 − 1) = τ (14 · 16) + τ (15 · 17) + τ (16 · 18) = 12 + 8 + 18 = 38 , where τ ( n ) is the number of divisors of n .