Difference between revisions of "2015 AMC 12B Problems/Problem 20"
(→Solution 2) |
|||
Line 61: | Line 61: | ||
Then <math>f(6,0)=f(5,1)=1</math>. Moreover, <math>f(6,n) = f(5,f(6,n-1)) = 1</math> for all <math>n</math>. Continuing in this manner we see that <math>f(m,n)=1</math> for all <math>m\ge 5</math>. | Then <math>f(6,0)=f(5,1)=1</math>. Moreover, <math>f(6,n) = f(5,f(6,n-1)) = 1</math> for all <math>n</math>. Continuing in this manner we see that <math>f(m,n)=1</math> for all <math>m\ge 5</math>. | ||
− | In particular | + | In particular, <math>f(2015,2) = \boxed{\textbf{(B)} \; 1}</math>. |
− | |||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2015|ab=B|num-a=21|num-b=19}} | {{AMC12 box|year=2015|ab=B|num-a=21|num-b=19}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 13:40, 26 December 2019
Contents
Problem
For every positive integer , let be the remainder obtained when is divided by 5. Define a function recursively as follows:
What is ?
Solution
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 .
Thus, .
Solution 2
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, .
See Also
2015 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 19 |
Followed by Problem 21 |
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.