返回题库

HMMT 二月 2018 · 冲刺赛 · 第 30 题

HMMT February 2018 — Guts Round — Problem 30

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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 .
解析

英文解析

  1. [ 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) .
    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 3 − 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 ≡ bfrom which we make the substitution − 1
    a = xy − 1
    b = yto 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
    ( 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 3 − 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 , andneither are 0. We have to worry about collisions between distinct values of x . There are two ways acollision 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.