Difference between revisions of "2015 AMC 12B Problems/Problem 20"
(→Solution 2) |
(→Solution) |
||
Line 11: | Line 11: | ||
<math>\textbf{(A)}\; 0 \qquad\textbf{(B)}\; 1 \qquad\textbf{(C)}\; 2 \qquad\textbf{(D)}\; 3 \qquad\textbf{(E)}\; 4</math> | <math>\textbf{(A)}\; 0 \qquad\textbf{(B)}\; 1 \qquad\textbf{(C)}\; 2 \qquad\textbf{(D)}\; 3 \qquad\textbf{(E)}\; 4</math> | ||
− | ==Solution== | + | ==Solution 1== |
Simply take some time to draw a table of values of <math>f(i,j)</math> for the first few values of <math>i</math>: | Simply take some time to draw a table of values of <math>f(i,j)</math> for the first few values of <math>i</math>: | ||
Line 34: | Line 34: | ||
Thus, <math>f(2015,2) = \boxed{\textbf{(B)} \; 1}</math>. | Thus, <math>f(2015,2) = \boxed{\textbf{(B)} \; 1}</math>. | ||
− | |||
− | |||
==Solution 2== | ==Solution 2== |
Latest revision as of 20:35, 9 December 2020
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 1
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.