Maths Olympiad Prep

Library / /540 of 740

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:

For an integer n0n \geq 0, let f(n)f(n) be the smallest possible value of x+y|x+y|, where xx and yy are integers such that 3x2y=n3x - 2y = n. Evaluate f(0)+f(1)+f(2)++f(2013)f(0) + f(1) + f(2) + \cdots + f(2013).

Solution

Solution:

Answer: 24162416

First, we can use 3x2y=n3x - 2y = n to get x=n+2y3x = \frac{n + 2y}{3}. Thus x+y=n+5y3|x + y| = \left| \frac{n + 5y}{3} \right|. Given a certain nn, the only restriction on yy is that 3n+2y3n+5y3 \mid n + 2y \Longleftrightarrow 3 \mid n + 5y. Hence the set of possible x+yx + y equals the set of integers of the form n+5y3\frac{n + 5y}{3}, which in turn equals the set of integers congruent to 31n2n(mod5)3^{-1} n \equiv 2n \pmod{5}. (Prove this!)

Thus f(n)=x+yf(n) = |x + y| is minimized when x+yx + y equals the least absolute remainder (2n)5(2n)_5 when 2n2n is divided by 55, i.e., the number between 2-2 and 22 (inclusive) congruent to 2n2n modulo 55. We immediately find f(n)=f(n+5m)f(n) = f(n + 5m) for all integers mm, and the following initial values of ff:

f(0)=(0)5=0f(0) = |(0)_5| = 0

f(1)=(2)5=2f(1) = |(2)_5| = 2

f(2)=(4)5=1f(2) = |(4)_5| = 1

f(3)=(6)5=1f(3) = |(6)_5| = 1

f(4)=(8)5=2f(4) = |(8)_5| = 2

Since 2013=403522013 = 403 \cdot 5 - 2, it follows that

f(0)+f(1)++f(2013)=403[f(0)+f(1)++f(4)]f(2014)=40362=2416. f(0) + f(1) + \cdots + f(2013) = 403 [f(0) + f(1) + \cdots + f(4)] - f(2014) = 403 \cdot 6 - 2 = 2416.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.