HMMT 二月 2018 · 冲刺赛 · 第 30 题
HMMT February 2018 — Guts Round — Problem 30
题目详情
- [ 17 ] Find the number of unordered pairs { a, b } , where a, b ∈ { 0 , 1 , 2 , . . . , 108 } such that 109 divides 3 3 a + b − ab .
解析
- [ 17 ] Find the number of unordered pairs { a, b } , where a, b ∈ { 0 , 1 , 2 , . . . , 108 } such that 109 divides 3 3 a + b − ab . Proposed by: Henrik Boecken Answer: 54 We start with the equation 3 3 a + b ≡ ab (mod 109) . 3 If either a or b are 0, then we get a ≡ 0, implying that both are 0. Thus, { 0 , 0 } is a pair. For the rest − 1 − 2 of the problem, let’s assume that neither a nor b are 0. Multiplying both sides by a b yields − 1 2 − 1 − 1 ( ab ) + a b ≡ b from which we make the substitution − 1 a = xy − 1 b = y to get the equation 2 − 1 y ≡ x + x . Plugging this value back into ( a, b ), we get that all solutions must be of the form − 2 − 1 2 − 1 − 1 ( a, b ) = (( x + x ) , ( x + x ) ) , − 2 2 where 1 ≤ x ≤ 108. It now suffices to find all nonzero unordered pairs { m, n } of the form { x + x , x + − 1 − 2 2 − 1 x } , where 1 ≤ x ≤ 108. There are four values of x for which x + x ≡ x + x , and of these values, − 2 three of them give x + x ≡ 0. This is because we can re-arrange the equation at hand to get 4 3 x − x + x − 1 ≡ 0 , which factors into 3 ( x − 1)( x + 1) ≡ 0 . 3 If x = 1, then { m, n } = { 2 , 2 } , and if x + 1 ≡ 0 (which has three solutions: 46 , 64 and 108), then − 1 3 − 2 3 { m, n } = { x ( x + 1) , x ( x + 1) } = { 0 , 0 } . Therefore, we keep x = 1 and discard x = 46 , 64 , 108. Of the remaining 104 values of x , m 6 = n , and neither are 0. We have to worry about collisions between distinct values of x . There are two ways a collision can occur: if there exists x 6 = y such that − 2 2 − 1 − 2 2 − 1 ( x + x , x + x ) = ( y + y , y + y ) , or if there exists x 6 = y such that − 2 2 − 1 2 − 1 − 2 ( x + x , x + x ) = ( y + y , y + y ) . − 2 − 2 2 − 1 − 2 − 2 The first case cannot occur: if x + x ≡ y + y , we have that x + x = x ( x + x ) 6 = y ( x + x ) = − 2 2 − 1 − 1 y ( y + y ) = y + y . As a consequence of this, the second case only occurs if y = x . Therefore, − 1 the remaining 104 values of x can be partitioned into 52 pairs of ( x, x ), which ends up producing 52 distinct unordered pairs { m, n } . Adding this to the x = 1 case and { 0 , 0 } , we get a total of 52 + 1 + 1 = 54 unordered pairs.