Maths Olympiad Prep

Library / /281 of 348

Algebra Difficulty 5.1 AIME, harder Find the answer

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=n3 x-2 y=n. Evaluate f(0)+f(1)+f(2)++f(2013)f(0)+f(1)+f(2)+\cdots+f(2013).

A number or a short expression. Spacing and $ signs are ignored.

Solution

First, we can use 3x2y=n3 x-2 y=n to get x=n+2y3x=\frac{n+2 y}{3}. Thus x+y=n+5y3|x+y|=\left|\frac{n+5 y}{3}\right|. Given a certain nn, the only restriction on yy is that 3n+2y3n+5y3|n+2 y \Longleftrightarrow 3| n+5 y. Hence the set of possible x+yx+y equals the set of integers of the form n+5y3\frac{n+5 y}{3}, which in turn equals the set of integers congruent to 31n2n(mod5)3^{-1} n \equiv 2 n(\bmod 5). (Prove this!) Thus f(n)=x+yf(n)=|x+y| is minimized when x+yx+y equals the least absolute remainder (2n)5(2 n)_{5} when 2n2 n is divided by 5, i.e. the number between -2 and 2 (inclusive) congruent to 2n2 n modulo 5. We immediately find f(n)=f(n+5m)f(n)=f(n+5 m) for all integers mm, and the following initial values of f:f(0)=(0)5=0f: f(0)=\left|(0)_{5}\right|=0; f(1)=(2)5=2;f(2)=(4)5=1;f(3)=(6)5=1f(1)=\left|(2)_{5}\right|=2 ; f(2)=\left|(4)_{5}\right|=1 ; f(3)=\left|(6)_{5}\right|=1; and f(4)=(8)5=2f(4)=\left|(8)_{5}\right|=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=2416f(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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.