HMMT 二月 2015 · 冲刺赛 · 第 34 题
HMMT February 2015 — Guts Round — Problem 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 6 10 ∑ nf ( n ) . n =1 b Write your answer in the form a · 10 , where b is an integer and 1 ≤ a < 10 is a decimal number. If your answer is written in this form, your score will be max { 0 , 25 − ⌊ 100 | log ( A/N ) |⌋ ) } , where 10 b N = a · 10 is your answer to this problem and A is the actual answer. Otherwise, your score will be zero.
解析
- [ 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 6 10 ∑ nf ( n ) . n =1 b Write your answer in the form a · 10 , where b is an integer and 1 ≤ a < 10 is a decimal number. If your answer is written in this form, your score will be max { 0 , 25 − ⌊ 100 | log ( A/N ) |⌋ ) } , where 10 b N = a · 10 is your answer to this problem and A is the actual answer. Otherwise, your score will be zero. 12 Answer: 1 . 813759629294 · 10 Rewrite the sum as ∑ 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 upper bound for this sum by noting that ( ) 2 3 x 3 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 ( ) 2 4 3 6 √ 10 + 1 ≈ 10 . 3 16 (We are throwing away “small” factors like in the approximation.) Furthermore, each term in the 3 6 12 12 sum is at most 10 , so the total sum is less than about 10 . The answer 1 · 10 would unfortunately still 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 2 2 ( x + xy + y ) dy dx = √ ( u + v ) dv du 2 2 6 2 2 6 3 x + xy + y ≤ 10 u + v ≤ 10 3 ∫ ∫ 2 π 10 2 3 √ = r dr dθ 3 0 0 3 ∫ 10 4 π 3 √ = r dr 3 0 π 12 = √ · 10 . 3 12 12 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+ 1e6) (defvar +lower+ -2000) (defvar +upper+ 2000) (princ Guts (loop for x from +lower+ to +upper+ sum (loop for y from +lower+ to +upper+ sum (let ((S (+ (* x x) (* x y) (* y y)))) (if (and (<= S +MAX+) (> S 0)) S 0)))))