HMMT 二月 2015 · 冲刺赛 · 第 34 题

英文解析

34. [ 25 ] For an integer n , let f ( n ) denote the number of pairs ( x, y ) of integers such that x + xy + y = n .
    Compute the sum
    ∑106
    nf ( n ) .
    n =1
    Write your answer in the form a · 10 , where b is an integer and 1 ≤ a < 10 is a decimal number.b
    If your answer is written in this form, your score will be max { 0 , 25 − ⌊ 100 | log ( A/N ) |⌋ ) } , whereb 10
    N = a · 10 is your answer to this problem and A is the actual answer. Otherwise, your score will bezero.
    Answer: 1 . 813759629294 · 10 Rewrite the sum as 12
    ∑
    2 2
    ( x + xy + y ) ,
    2 2 6
    x + xy + y ≤ 10
    2 2 6
    where the sum is over all pairs ( x, y ) of integers with x + xy + y ≤ 10 . We can find a crude upperbound for this sum by noting that
    ( )
    3 x 32
    2 2 2 2
    x + xy + y = x + + y ≥ x ,
    4 2 4
    2 2
    3 3
    √ √
    so each term of this sum has | x | ≤ 10 . Similarly, | y | ≤ 10 . Therefore, the number of terms in
    3 3
    the sum is at most
    ( )
    3 642
    √
    10 + 1 ≈ 10 .
    (We are throwing away “small” factors like in the approximation.) Furthermore, each term in the 163
    6 12 123
    sum is at most 10 , so the total sum is less than about 10 . The answer 1 · 10 would unfortunatelystill get a score of 0.
    For a better answer, we can approximate the sum by an integral:
    ∫ ∫
    ∑
    2 2 2 2
    ( x + xy + y ) ≈ ( x + xy + y ) dy dx.
    2 2 6
    x + xy + y ≤ 10
    2 2 6
    x + xy + y ≤ 10
    ( )
    √
    3 1
    Performing the change of variables ( u, v ) = x, x + y and then switching to polar coordinates
    2 2
    √
    − 1
    2 2
    ( r, θ ) = ( u + v , tan ( v/u )) yields
    ∫ ∫ ∫ ∫
    2 2 2 22
    ( x + xy + y ) dy dx = √ ( u + v ) dv du
    2 2 6 2 2 6
    x + xy + y ≤ 10 u + v ≤ 103
    ∫ ∫3
    2 π 10
    √32 = r dr dθ
    0 03
    ∫3
    4 π10
    √3 = r drπ03 = √ · 10 .12
    12 123
    This is approximately 1 . 8138 · 10 , which is much closer to the actual answer. (An answer of 1 . 8 · 10
    is good enough for full credit.)
    The answer can also be computed exactly by the Common Lisp code:
    (defconstant +MAX+ 1 e 6)
    (defvar +lower+ -2000)
    (defvar +upper+ 2000)
    (princ
    Guts
    (loop for x from +lower+ to +upper+ sum
    (loop for y from +lower+ to +upper+
    (let ((S (+ (* x x) (* x y) (* y y))))sum
    (if (and (<= S +MAX+) (> S 0)) S 0)))))