2000 AIME I Problem 12

Below is the professionally curated solution for Problem 12 of the 2000 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:functional equationgreatest common divisorsymmetry

Difficulty rating: 2920

12.

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

Solution:

Since f(398x)=f(2158x)f(398 - x) = f(2158 - x) for all x,x, substituting t=398xt = 398 - x gives f(t)=f(t+1760);f(t) = f(t + 1760); likewise f(2158x)=f(3214x)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(398x)f(x) = f(398 - x) becomes f(x)=f(46x).f(x) = f(46 - x).

So ff is determined by residues mod 352,352, with residues rr and 46r46 - r forced to share a value. This pairing has exactly two fixed points, from 2r46(mod352):2r \equiv 46 \pmod{352}: r=23r = 23 and r=199.r = 199. Hence there are at most 35222+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)=cos2π(x23)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 11Full ExamProblem 13

Problem 12 in Other Years