2000 AIME I Problem 12

Attempt Problem 12 of the 2000 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2000 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Given a function ff for which f(x)=f(398−x)=f(2158−x)=f(3214−x) \begin{aligned} f(x) &= f(398 - x) \\ &= f(2158 - x) \\ &= f(3214 - x) \end{aligned} holds for all real x,x, what is the largest number of different values that can appear in the list f(0),f(0), f(1),f(1), f(2),f(2), …,\ldots, f(999)?f(999)?

Answer: 177
Concepts:functional equationgreatest common divisorsymmetry
Difficulty rating: 2920
Small Hint:

Two reflection symmetries compose to a translation: f(398−x)=f(2158−x)f(398 - x) = f(2158 - x) forces f(t)=f(t+1760),f(t) = f(t + 1760), and similarly f(t)=f(t+1056)f(t) = f(t + 1056)

Big Hint:

So ff has period gcd⁡(1760,1056)=352,\gcd(1760, 1056) = 352, plus the symmetry f(x)=f(46−x);f(x) = f(46 - x); count residues mod 352352 up to that pairing

Solution:

Since f(398−x)=f(2158−x)f(398 - x) = f(2158 - x) for all x,x, substituting t=398−xt = 398 - x gives f(t)=f(t+1760);f(t) = f(t + 1760); likewise f(2158−x)=f(3214−x)f(2158 - x) = f(3214 - x) gives period 1056.1056. Combining, ff has period gcd⁡(1760,1056)=352.\gcd(1760, 1056) = 352. Reducing 398398 mod 352,352, the symmetry f(x)=f(398−x)f(x) = f(398 - x) becomes f(x)=f(46−x).f(x) = f(46 - x).

So ff is determined by residues mod 352,352, with residues rr and 46−r46 - r forced to share a value. This pairing has exactly two fixed points, from 2r≡46(mod352):2r \equiv 46 \pmod{352}: r=23r = 23 and r=199.r = 199. Hence there are at most 352−22+2=177\frac{352 - 2}{2} + 2 = 177 classes, and since 0,1,…,9990, 1, \ldots, 999 covers every residue mod 352,352, the list contains at most 177177 different values.

This is achievable: f(x)=cos⁡2π(x−23)352f(x) = \cos\frac{2\pi(x - 23)}{352} satisfies all three given symmetries (each of 398,398, 2158,2158, 32143214 is ≡46\equiv 46 mod 352352), and two integers get equal values only when their residues are paired. So the answer is 177.177.

Problem 11#11
Full Exam

Problem 12 in Other Years