Difference between revisions of "2015 AMC 12B Problems/Problem 20"
m (30 minutes is unrealistic for the 75 min competition.) |
|||
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== | ||
+ | |||
+ | We are given that <cmath> f(0,n) \equiv n+1\pmod{5} .</cmath> | ||
+ | Then, <math>f(1,n) = f(0, f(1, n-1)) \equiv f(1,n-1) + 1\pmod{5}</math>. Thus <math>f(1,n) \equiv n+f(1,0)\pmod{5}</math>. Since <math>f(1,0)=f(0,1)=2</math>, we get | ||
+ | <cmath>f(1,n) \equiv n+2\pmod{5} .</cmath> | ||
+ | Then, <math>f(2,n) = f(1, f(2, n-1)) \equiv f(2,n-1) + 2\pmod{5}</math>. Thus <math>f(2,n) \equiv 2n+f(2,0)\pmod{5}</math>. Since <math>f(2,0)=f(1,1)=3</math>, we get | ||
+ | <cmath>f(2,n) \equiv 2n+3\pmod{5} .</cmath> | ||
+ | Now <math>f(3,n) = f(2, f(3, n-1)) \equiv 2f(3,n-1) + 3\pmod{5}</math>. Thus | ||
+ | <cmath>\begin{align*} | ||
+ | f(3,n) &\equiv 2f(3,n-1) + 3 &\pmod{5} \\ | ||
+ | 2f(3,n-1) &\equiv 2^2f(3,n-2) + 3\cdot 2 &\pmod{5} \\ | ||
+ | \vdots \qquad &\quad\vdots \quad\qquad \vdots \qquad\qquad \vdots &\\ | ||
+ | 2^{n-1}f(3,1) &\equiv 2^nf(3,0) + 3\cdot 2^{n-1} &\pmod{5} | ||
+ | \end{align*}</cmath> | ||
+ | Adding them all up we get | ||
+ | <cmath>f(3,n) \equiv 3(2^n-1)\pmod{5} .</cmath> | ||
+ | This means that <math>f(3,0)=0</math>, <math>f(3,1)=3</math>, <math>f(3,2)=4</math>, <math>f(3,3)=1</math>, and <math>f(3,4)=0</math>. Thus <math>f(3,n)</math> never takes the value 2. | ||
+ | |||
+ | Since <math>f(4,n)=f(3,f(4,n-1))</math>, this implies that <math>f(4,n) \neq 2</math> for any <math>n</math>. By induction, <math>f(3,n) \neq f(3,2) = 4</math> for any <math>n</math>. It follows that <math>f(3,n) \neq f(3,4) = 0</math> for any <math>n</math>. Thus <math>f(4,n)</math> only takes values in <math>\{1,3\}</math>. In fact, it alternates between 1 and 3: <math>f(4,0)=f(3,1)=3</math>, then <math>f(4,1)=f(3,f(4,0))=f(3,3)=1</math>, then <math>f(4,2)=f(3,f(4,1))=f(3,1)=3</math>, and so on. | ||
+ | |||
+ | Repeating the argument above, we see that <math>f(5,n) = f(4, f(5,n-1))</math> can only take values in <math>\{1,3\}</math>. However, <math>f(5,n-1)\neq 0</math> for any <math>n</math> implies that <math>f(5,n)\neq f(4,0)=3</math> for any <math>n</math>. Thus <math>f(5,n)=1</math> for all <math>n</math>. We can easily verify this: <math>f(5,0)=f(4,1)=1</math>, then <math>f(5,1)=f(4,f(5,0))=f(4,1)=1</math>, then <math>f(5,2)=f(4,f(5,1))=f(4,1)=1</math>, and so on. | ||
+ | |||
+ | 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, Thus, <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 14:39, 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, 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.