HMMT 十一月 2013 · 团队赛 · 第 9 题

HMMT November 2013 — Team Round — Problem 9

[ 7 ] For an integer n ≥ 0, let f ( n ) be the smallest possible value of | x + y | , where x and y are integers such that 3 x − 2 y = n . Evaluate f (0) + f (1) + f (2) + · · · + f (2013). 2 π 2 π

解析

[ 7 ] For an integer n ≥ 0, let f ( n ) be the smallest possible value of | x + y | , where x and y are integers such that 3 x − 2 y = n . Evaluate f (0) + f (1) + f (2) + · · · + f (2013). n +2 y n +5 y Answer: 2416 First, we can use 3 x − 2 y = n to get x = . Thus | x + y | = | | . Given 3 3 a certain n , the only restriction on y is that 3 | n + 2 y ⇐⇒ 3 | n + 5 y . Hence the set of possible n +5 y x + y equals the set of integers of the form , which in turn equals the set of integers congruent to 3 − 1 3 n ≡ 2 n (mod 5). (Prove this!) Thus f ( n ) = | x + y | is minimized when x + y equals the least absolute remainder (2 n ) when 2 n is 5 divided by 5, i.e. the number between − 2 and 2 (inclusive) congruent to 2 n modulo 5. We immediately find f ( n ) = f ( n + 5 m ) for all integers m , and the following initial values of f : f (0) = | (0) | = 0; 5 f (1) = | (2) | = 2; f (2) = | (4) | = 1; f (3) = | (6) | = 1; and f (4) = | (8) | = 2. 5 5 5 5 Since 2013 = 403 · 5 − 2, it follows that f (0)+ f (1)+ · · · + f (2013) = 403[ f (0)+ f (1)+ · · · + f (4)] − f (2014) = 403 · 6 − 2 = 2416. 2 π 2 π