2000 AIME I Problems/Problem 12

Problem

Given a function for which holds for all real what is the largest number of different values that can appear in the list

Solution

Since we can conclude that (by the Euclidean algorithm)

So we need only to consider one period , which can have at most distinct values which determine the value of at all other integers.

But we also know that , so the values and are repeated. This gives a total of

distinct values.

To show that it is possible to have distinct, we try to find a function which fulfills the given conditions. A bit of trial and error would lead to the cosine function: (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 , as if a function can be expressed with it must be symmetric against line . Try this yourself by graphing a polynomial , then graphing . If , their point of intersection at must contain a line of symmetry.

For this particular function , it has lines of symmetry already given: , , and . Now imagine these lines of symmetry folding over each other to form new lines of symmetry, because should have another corresponding line of symmetry when being reflected over the lines and due to it being, well, symmetric. Doing so, we find that there will be two new lines of symmetry generated by folding over the other 2 lines of symmetry, namely, and . Now, if we fold 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 over 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 over to obtain . We now fold over to find . Now we fold over to get . Now we fold over to find , then we fold over , then fold over that line again, until suddenly, we find that after doing a few folds, there will be a line that coincides with . Now, if you visualize a graph of all the lines of symmetry, you will find that from to , there will lines of symmetry evenly spaced by units each. If fold and 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 units. This tells us that the half period of is units, which means that every units, the y-values will repeat. Now, all we have to do is put in the answer .

Why , you ask, and not ?

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 , we see that every units it repeats. Every 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

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