HMMT 二月 2008 · 冲刺赛 · 第 31 题

英文解析

31. [ 18 ] Let C be the hyperbola y − x = 1. Given a point P on the x -axis, we construct a sequenceof points ( P ) on the x -axis in the following manner: let be the line with slope 1 passing passing 0 n nthrough P , then P is the orthogonal projection of the point of intersection of and C onto the 8
    n n +1 nx -axis. (If P = 0, then the sequence simply terminates.)
    Let N be the number of starting positions P on the x -axis such that P = P . Determine then
    0 0 2008
    remainder of N when divided by 2008.
    Answer: 254 Let P = ( x , 0). Then the ` meet C at ( x , x − x ). Since this point lies onn n n n +1 n +1 n
    2 2
    the hyperbola, we have ( x − x ) − x = 1. Rearranging this equation givesn +1 nn +1
    x − 12
    x = .nn +1
    2 xn
    Choose a θ ∈ (0 , π ) with cot θ = x , and define θ = 2 θ . Using the double-angle formula, we haven
    0 0 0 n 0
    cot θ − 12
    cot θ = cot(2 θ ) = .nn +1 n
    2 cot θn
    ( )
    2008
    It follows by induction that x = cot θ . Then, P = P corresponds to cot θ = cot 2 θn n 0 2008 0 0
    (assuming that P is never at the origin, or equivalently, 2 θ is never an integer multiple of π ). So, wen
    20080
    need to find the number of θ ∈ (0 , π ) with the property that 2 θ − θ = kπ for some integer k . We
    0 0 0
    2008 kπhave θ = , so k can be any integer between 1 and 2 − 2 inclusive (and note that since the
    0 2008
    2 − 1
    denominator is odd, the sequence never terminates). It follows that the number of starting positions
    2008
    is N = 2 − 2.
    Finally, we need to compute the remainder when N is divided by 2008. We have 2008 = 2 × 251.3
    ( )
    2008 250 44
    Using Fermat’s Little Theorem with 251, we get 2 ≡ 2 · 256 ≡ 1 · 5 = 5 (mod 251). So wehave N ≡ 3 (mod 251) and N ≡ − 2 (mod 8). Using Chinese Remainder Theorem, we get N ≡ 254
    (mod 2008).