2015 AMC 12B Problems/Problem 20
Problem
For every positive integer 
, let 
be the remainder obtained when is divided by 5. Define a function 
recursively as follows:
![\[f(i,j) = \begin{cases}\text{mod}_5 (j+1) & \text{ if } i = 0 \text{ and } 0 \le j \le 4 \text{,}\\ f(i-1,1) & \text{ if } i \ge 1 \text{ and } j = 0 \text{, and} \\ f(i-1, f(i,j-1)) & \text{ if } i \ge 1 \text{ and } 1 \le j \le 4. \end{cases}\]](http://latex.artofproblemsolving.com/1/e/f/1efa0d34cf7ae66e852b1687a71b18515cda058b.png)
What is 
?
Solution
Simply take some time to draw a table of values of 
for the first few values of 
:
![\[\begin{array}{|c || c | c | c | c | c |} \hline i \text{\ \textbackslash\ } j & 0 & 1 & 2 & 3 & 4\\ \hline\hline 0 & 1 & 2 & 3 & 4 & 0\\ \hline 1 & 2 & 3 & 4 & 0 & 1\\ \hline 2 & 3 & 0 & 2 & 4 & 1\\ \hline 3 & 0 & 3 & 4 & 1 & 0\\ \hline 4 & 3 & 1 & 3 & 1 & 3\\ \hline 5 & 1 & 1 & 1 & 1 & 1\\ \hline \end{array}\]](http://latex.artofproblemsolving.com/8/6/a/86a0e49932036b4f8ac2202543492e3c25dc10c6.png)
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, 
.
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. 
