2015 AMC 12B Problems/Problem 20
For every positive integer , let be the remainder obtained when is divided by 5. Define a function recursively as follows:
What is ?
Simply take some time to draw a table of values of for the first few values of :
Now we claim that for , for all values . We will prove this by induction on and . The base cases for , have already been proven.
For our inductive step, we must show that for all valid values of , if for all valid values of , .
We prove this itself by induction on . For the base case, , . For the inductive step, we need if . Then, by our inductive hypothesis from our inner induction and from our outer inductive hypothesis. Thus, , completing the proof.
It is now clear that for , for all values .
We are given that Then, . Thus . Since , we get Then, . Thus . Since , we get Now . Thus Adding them all up we get This means that , , , , and . Thus never takes the value 2.
Since , this implies that for any . By induction, for any . It follows that for any . Thus only takes values in . In fact, it alternates between 1 and 3: , then , then , and so on.
Repeating the argument above, we see that can only take values in . However, for any implies that for any . Thus for all . We can easily verify this: , then , then , and so on.
Then . Moreover, for all . Continuing in this manner we see that for all .
In particular, Thus, .
|2015 AMC 12B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|