Number theoryDifficulty 5.2AIME, harderProve itUnited States
Problem:
For an integer n≥0, let f(n) be the smallest possible value of ∣x+y∣, where x and y are integers such that 3x−2y=n. Evaluate f(0)+f(1)+f(2)+⋯+f(2013).
Solution
Solution:
Answer: 2416
First, we can use 3x−2y=n to get x=3n+2y. Thus ∣x+y∣=3n+5y. Given a certain n, the only restriction on y is that 3∣n+2y⟺3∣n+5y. Hence the set of possible x+y equals the set of integers of the form 3n+5y, which in turn equals the set of integers congruent to 3−1n≡2n(mod5). (Prove this!)
Thus f(n)=∣x+y∣ is minimized when x+y equals the least absolute remainder (2n)5 when 2n is divided by 5, i.e., the number between −2 and 2 (inclusive) congruent to 2n modulo 5. We immediately find f(n)=f(n+5m) for all integers m, and the following initial values of f: