Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2000 AIME I Problems/Problem 12"

(→‎Solution)
(→‎Solution 2)
 
(4 intermediate revisions by the same user not shown)
Line 24: Line 24:
  
 
== Solution 2 ==
 
== Solution 2 ==
−
    One can imagine that there must be multiple lines of symmetry for the function <math>f(x)</math>, as if a function can be expressed with <math>f(x)=f(a-x)</math> it must be symmetric against line <math>x=\frac{a}{2}</math>. Try this yourself by graphing a polynomial <math>f(x)=x^a</math>, then graphing <math>f(n-x)</math>. If <math>f(x)=f(n-x)</math>, their point of intersection at <math>x=\frac{n}{2}</math> must contain a line of symmetry.
+
 
 +
This gives the intuition the first solution uses to solve the problem.
 +
 
 +
One can imagine that there must be multiple lines of symmetry for the function <math>f(x)</math>, as if a function can be expressed with <math>f(x)=f(a-x)</math> it must be symmetric against line <math>x=\frac{a}{2}</math>. Try this yourself by graphing a polynomial <math>f(x)</math>, then graphing <math>f(n-x)</math>. If <math>f(x)=f(n-x)</math>, their point of intersection at <math>x=\frac{n}{2}</math> must contain a line of symmetry.
  
−
    For this particular function <math>f(x)</math>, it has 3 other values
+
For this particular function <math>f(x)</math>, it has <math>3</math> lines of symmetry already given: <math>x=199</math>, <math>x=1079</math>, and <math>x=1607</math>. Now imagine these lines of symmetry folding over each other to form new lines of symmetry, because <math>x=199</math> should have another corresponding line of symmetry when being reflected over the lines <math>x=1079</math> and <math>x=1607</math> due to it being, well, symmetric. Doing so, we find that there will be two new lines of symmetry generated by folding <math>x=199</math> over the other 2 lines of symmetry, namely, <math>x=1079+(1079-199)=1959</math> and <math>x=1607+(1607-199)=3015</math>. Now, if we fold <math>x=1079</math> over the other 2 lines of symmetry, we will find another 2 lines of symmetry. We can even fold lines of symmetry not originally given by the problem, such as <math>x=3015</math> over <math>x=1959</math> to form even more lines of symmetry. This will result in infinite lines of symmetry, which tells us that this function is periodic.
 +
 
 +
As we have just proven that f(x) has a finite amount of values, now, we need to find what the half period it is, and not a whole period because in periodic functions such as cos(x), the y values will repeat every half period and not a full period. To do this, we go back to the 3 lines of symmetry given by the problem, and we fold <math>x=1607</math> over <math>x=1079</math> to obtain <math>x=1079-(1607-1079)=551</math>. We now fold <math>x=551</math> over <math>x=199</math> to find <math>x=199-(551-199)=-153</math>. Now we fold <math>x=-153</math> over <math>x=551</math> to get <math>x=551+(551-(-153))=1255</math>. Now we fold <math>x=1255</math> over <math>x=1079</math> to find <math>x=903</math>, then we fold <math>x=1079</math> over <math>x=903</math>, then fold <math>x=903</math> over that line again, until suddenly, we find that after doing a few folds, there will be a line that coincides with <math>x=199</math>. Now, if you visualize a graph of all the lines of symmetry, you will find that from <math>x=199</math> to <math>x=1079</math>, there will lines of symmetry evenly spaced by <math>176</math> units each. If fold <math>x=1255</math> and <math>x=1079</math> in the other direction, you will find that it will coincide with all other named lines of symmetry and extend to infinity, with one line of symmetry every <math>176</math> units. This tells us that the half period of <math>f(x)</math> is <math>176</math> units, which means that every <math>176</math> units, the y-values will repeat. Now, all we have to do is put in the answer <math>\fbox{177}</math>.
 +
 
 +
 
 +
 
 +
Why <math>177</math>, you ask, and not <math>176</math>?
 +
 
 +
Imagine a square composed of unit squares. You can find the amount of unit squares on the perimeter of the large square by taking the side length of the larger square, subtracting one, then multiplying by 4. This is not the same as finding the perimeter because if you simply found the perimeter, you would have overcounted the 4 squares on the corners. Using the same intuition, in our periodic function <math>f(x)</math>, we see that every <math>176</math> units it repeats. Every <math>176</math> units, it will have counted not the total amount of values, but the total amount of values minus one. That's why we need to add 1 to our answer.
 +
 
 +
 
 +
 
 +
-WhatdoHumanitariansEat
  
 
== See also ==
 
== See also ==

Latest revision as of 15:36, 28 November 2024

Problem

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

Solution

\begin{align*}f(2158 - x) = f(x) &= f(3214 - (2158 - x)) &= f(1056 + x)\\ f(398 - x) = f(x) &= f(2158 - (398 - x)) &= f(1760 + x)\end{align*}

Since $\mathrm{gcd}(1056, 1760) = 352$ we can conclude that (by the Euclidean algorithm)

\[f(x) = f(352 + x)\]

So we need only to consider one period $f(0), f(1), ... f(351)$, which can have at most $352$ distinct values which determine the value of $f(x)$ at all other integers.

But we also know that $f(x) = f(46 - x) = f(398 - x)$, so the values $x = 24, 25, ... 46$ and $x = 200, 201, ... 351$ are repeated. This gives a total of

\[352 - (46 - 24 + 1) - (351 - 200 + 1) = \boxed{ 177 }\]

distinct values.

To show that it is possible to have $f(23), f(24), \ldots, f(199)$ distinct, we try to find a function which fulfills the given conditions. A bit of trial and error would lead to the cosine function: $f(x) = \cos \left(\frac{360}{352}(x-23)\right)$ (in degrees).

Solution 2

This gives the intuition the first solution uses to solve the problem.

One can imagine that there must be multiple lines of symmetry for the function $f(x)$, as if a function can be expressed with $f(x)=f(a-x)$ it must be symmetric against line $x=\frac{a}{2}$. Try this yourself by graphing a polynomial $f(x)$, then graphing $f(n-x)$. If $f(x)=f(n-x)$, their point of intersection at $x=\frac{n}{2}$ must contain a line of symmetry.

For this particular function $f(x)$, it has $3$ lines of symmetry already given: $x=199$, $x=1079$, and $x=1607$. Now imagine these lines of symmetry folding over each other to form new lines of symmetry, because $x=199$ should have another corresponding line of symmetry when being reflected over the lines $x=1079$ and $x=1607$ due to it being, well, symmetric. Doing so, we find that there will be two new lines of symmetry generated by folding $x=199$ over the other 2 lines of symmetry, namely, $x=1079+(1079-199)=1959$ and $x=1607+(1607-199)=3015$. Now, if we fold $x=1079$ over the other 2 lines of symmetry, we will find another 2 lines of symmetry. We can even fold lines of symmetry not originally given by the problem, such as $x=3015$ over $x=1959$ to form even more lines of symmetry. This will result in infinite lines of symmetry, which tells us that this function is periodic.

As we have just proven that f(x) has a finite amount of values, now, we need to find what the half period it is, and not a whole period because in periodic functions such as cos(x), the y values will repeat every half period and not a full period. To do this, we go back to the 3 lines of symmetry given by the problem, and we fold $x=1607$ over $x=1079$ to obtain $x=1079-(1607-1079)=551$. We now fold $x=551$ over $x=199$ to find $x=199-(551-199)=-153$. Now we fold $x=-153$ over $x=551$ to get $x=551+(551-(-153))=1255$. Now we fold $x=1255$ over $x=1079$ to find $x=903$, then we fold $x=1079$ over $x=903$, then fold $x=903$ over that line again, until suddenly, we find that after doing a few folds, there will be a line that coincides with $x=199$. Now, if you visualize a graph of all the lines of symmetry, you will find that from $x=199$ to $x=1079$, there will lines of symmetry evenly spaced by $176$ units each. If fold $x=1255$ and $x=1079$ in the other direction, you will find that it will coincide with all other named lines of symmetry and extend to infinity, with one line of symmetry every $176$ units. This tells us that the half period of $f(x)$ is $176$ units, which means that every $176$ units, the y-values will repeat. Now, all we have to do is put in the answer $\fbox{177}$.


Why $177$, you ask, and not $176$?

Imagine a square composed of unit squares. You can find the amount of unit squares on the perimeter of the large square by taking the side length of the larger square, subtracting one, then multiplying by 4. This is not the same as finding the perimeter because if you simply found the perimeter, you would have overcounted the 4 squares on the corners. Using the same intuition, in our periodic function $f(x)$, we see that every $176$ units it repeats. Every $176$ units, it will have counted not the total amount of values, but the total amount of values minus one. That's why we need to add 1 to our answer.


-WhatdoHumanitariansEat

See also

2000 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_I_Problems/Problem_12&oldid=235767"