Maths Olympiad Prep

Library / HMMT November /413 of 672

HMMT November

Algebra Difficulty 5.1 AIME, harder Find the answer

For an integer n≥0n \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 3x−2y=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. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

First, we can use 3x−2y=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 3∣n+2y⟺3∣n+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 3−1n≡2n( mod 5)3^{-1} n \equiv 2 n(\bmod 5). (Prove this!) Thus f(n)=∣x+y∣f(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=403⋅5−22013=403 \cdot 5-2, it follows that f(0)+f(1)+⋯+f(2013)=403[f(0)+f(1)+⋯+f(4)]−f(2014)=403⋅6−2=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.