Difference between revisions of "2018 AMC 10B Problems/Problem 20"

(Solution 4 (Algebra))
m (Solution 5 (Bash))
(46 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2018 AMC 12B Problems|2018 AMC 12B #18]] and [[2018 AMC 10B Problems|2018 AMC 10B #20]]}}
 +
 
==Problem==
 
==Problem==
  
 
A function <math>f</math> is defined recursively by <math>f(1)=f(2)=1</math> and <cmath>f(n)=f(n-1)-f(n-2)+n</cmath>for all integers <math>n \geq 3</math>. What is <math>f(2018)</math>?
 
A function <math>f</math> is defined recursively by <math>f(1)=f(2)=1</math> and <cmath>f(n)=f(n-1)-f(n-2)+n</cmath>for all integers <math>n \geq 3</math>. What is <math>f(2018)</math>?
  
<math>\textbf{(A)} \text{ 2016} \qquad \textbf{(B)} \text{ 2017} \qquad \textbf{(C)} \text{ 2018} \qquad \textbf{(D)} \text{ 2019} \qquad \textbf{(E)} \text{ 2020}</math>
+
<math>\textbf{(A) } 2016 \qquad \textbf{(B) } 2017 \qquad \textbf{(C) } 2018 \qquad \textbf{(D) } 2019 \qquad \textbf{(E) } 2020</math>
 +
 
 +
==Solution 1 (Algebra)==
 +
For all integers <math>n \geq 7,</math> note that
 +
<cmath>\begin{align*}
 +
f(n)&=f(n-1)-f(n-2)+n \\
 +
&=[f(n-2)-f(n-3)+n-1]-f(n-2)+n \\
 +
&=-f(n-3)+2n-1 \\
 +
&=-[f(n-4)-f(n-5)+n-3]+2n-1 \\
 +
&=-f(n-4)+f(n-5)+n+2 \\
 +
&=-[f(n-5)-f(n-6)+n-4]+f(n-5)+n+2 \\
 +
&=f(n-6)+6.
 +
\end{align*}</cmath>
 +
It follows that
 +
<cmath>\begin{align*}
 +
f(2018)&=f(2012)+6 \\
 +
&=f(2006)+12 \\
 +
&=f(2000)+18 \\
 +
& \ \vdots \\
 +
&=f(2)+2016 \\
 +
&=\boxed{\textbf{(B) } 2017}.
 +
\end{align*}</cmath>
 +
~MRENTHUSIASM
 +
 
 +
==Solution 2 (Algebra)==
 +
For all integers <math>n\geq3,</math> we rearrange the given equation: <cmath>f(n)-f(n-1)+f(n-2)=n. \hspace{28.25mm}(1)</cmath>
 +
For all integers <math>n\geq4,</math> it follows that <cmath>f(n-1)-f(n-2)+f(n-3)=n-1. \hspace{15mm}(2)</cmath>
 +
For all integers <math>n\geq4,</math> we add <math>(1)</math> and <math>(2):</math> <cmath>f(n)+f(n-3)=2n-1. \hspace{38.625mm}(3)</cmath>
 +
For all integers <math>n\geq7,</math> it follows that <cmath>f(n-3)+f(n-6)=2n-7. \hspace{32mm}(4)</cmath>
 +
For all integers <math>n\geq7,</math> we subtract <math>(4)</math> from <math>(3):</math> <cmath>f(n)-f(n-6)=6. \hspace{47.5mm}(5)</cmath>
 +
From <math>(5),</math> we have the following system of <math>336</math> equations:
 +
<cmath>\begin{align*}
 +
f(2018)-f(2012)&=6, \\
 +
f(2012)-f(2006)&=6, \\
 +
f(2006)-f(2000)&=6, \\
 +
& \ \vdots \\
 +
f(8)-f(2)&=6.
 +
\end{align*}</cmath>
 +
We add these equations up to get <cmath>f(2018)-f(2)=6\cdot336=2016,</cmath> from which <math>f(2018)=f(2)+2016=\boxed{\textbf{(B) } 2017}.</math>
 +
 
 +
~AopsUser101 ~MRENTHUSIASM
  
==Solution 1==
+
==Solution 3 (Finite Differences)==
<math>f\left(n\right) = f\left(n - 1\right) - f\left(n - 2\right) + n</math>
 
  
<math>= \left(f\left(n - 2\right) - f\left(n - 3\right) + n - 1\right) - f\left(n - 2\right) + n</math>
+
Preamble: In this solution, we define the sequence <math>A</math> to satisfy <math>a_n = f(n),</math> where <math>a_n</math> represents the <math>n</math>th term of the sequence <math>A.</math> This solution will show a few different perspectives. Even though it may not be as quick as some of the solutions above, I feel like it is an interesting concept, and may be more motivated.
  
<math>= 2n - 1 - f\left(n - 3\right)</math>
+
To begin, we consider the sequence <math>B</math> formed when we take the difference of consecutive terms between <math>A.</math> Define <math>b_n = a_{n+1} - a_n.</math> Notice that for <math>n \ge 4,</math> we have <center><math>\begin{cases}\begin{aligned} a_{n+1} &= a_{n} - a_{n-1} + (n+1) \\ a_{n} &= a_{n-1} - a_{n-2} + n \end{aligned}.\end{cases}</math></center> Notice that subtracting the second equation from the first, we see that <math>b_{n} = b_{n-1} - b_{n-2} + 1.</math>  
  
<math>= 2n - 1 - \left(2\left(n - 3\right) - 1 - f\left(n - 6\right)\right)</math>
+
If you didn’t notice that <math>B</math> repeated directly in the solution above, you could also, possibly more naturally, take the finite differences of the sequence <math>b_n</math> so that you could define <math>c_n = b_{n+1} - b_n.</math> Using a similar method as above through reindexing and then subtracting, you could find that <math>c_n = c_{n-1} - c_{n-2}.</math> The sum of any six consecutive terms of a sequence which satisfies such a recursion is <math>0,</math> in which you have that <math>b_{n} = b_{n+6}.</math> In the case in which finite differences didn’t reduce to such a special recursion, you could still find the first few terms of <math>C</math> to see if there are any patterns, now that you have a much simpler sequence. Doing so in this case, it can also be seen by seeing that the sequence <math>C</math> looks like <cmath>\underbrace{2, 1, -1, -2, -1, 1,}_{\text{cycle period}} 2, 1, -1, -2, -1, 1, \ldots</cmath> in which the same result follows.
  
<math>= f\left(n - 6\right) + 6</math>
+
Using the fact that <math>B</math> repeats every six terms, this motivates us to look at the sequence <math>B</math> more carefully. Doing so, we see that <math>B</math> looks like <cmath>\underbrace{2, 3, 2, 0, -1, 0,}_{\text{cycle period}} 2, 3, 2, 0, -1, 0, \ldots</cmath> (If you tried pattern finding on sequence <math>B</math> directly, you could also arrive at this result, although I figured defining a second sequence based on finite differences was more motivated.)
  
Thus, <math>f\left(2018\right) = 2016 + f\left(2\right) = 2017</math>. <math>\boxed{B}</math>
+
Now, there are two ways to finish.  
  
==Solution 2 (A Bit Bashy)==
+
Finish Method #1: Notice that any six consecutive terms of <math>B</math> sum to <math>6,</math> after which we see that <math>a_n = a_{n-6} + 6.</math> Therefore, <math>a_{2018} = a_{2012} + 6 = \cdots = a_{2} + 2016 = \boxed{\textbf{(B) } 2017}.</math>
Start out by listing some terms of the sequence.
 
<cmath>f(1)=1</cmath>
 
<cmath>f(2)=1</cmath>
 
  
<cmath>f(3)=3</cmath>
+
Finish Method #2: Notice that <math>a_{2018} = a_{2017} - a_{2016} + 2018 = B_{2016} + 2018 = -1 + 2018 = \boxed{\textbf{(B) } 2017}.</math>  
<cmath>f(4)=6</cmath>
 
<cmath>f(5)=8</cmath>
 
<cmath>f(6)=8</cmath>
 
<cmath>f(7)=7</cmath>
 
<cmath>f(8)=7</cmath>
 
  
<cmath>f(9)=9</cmath>
+
~Professor-Mom
<cmath>f(10)=12</cmath>
 
<cmath>f(11)=14</cmath>
 
<cmath>f(12)=14</cmath>
 
<cmath>f(13)=13</cmath>
 
<cmath>f(14)=13</cmath>
 
  
<cmath>f(15)=15</cmath>
+
==Solution 4 (Bash)==
<cmath>.....</cmath>
+
Start out by listing some terms of the sequence.
Notice that <math>f(n)=n</math> whenever <math>n</math> is an odd multiple of <math>3</math>, and the pattern of numbers that follow will always be +3, +2, +0, -1, +0.
+
<cmath>\begin{align*}
 +
f(1)&=1 \\
 +
f(2)&=1 \\
 +
f(3)&=3 \\
 +
f(4)&=6 \\
 +
f(5)&=8 \\
 +
f(6)&=8 \\
 +
f(7)&=7 \\
 +
f(8)&=7 \\
 +
f(9)&=9 \\
 +
f(10)&=12 \\
 +
f(11)&=14 \\
 +
f(12)&=14 \\
 +
f(13)&=13 \\
 +
f(14)&=13 \\
 +
f(15)&=15 \\
 +
& \ \vdots
 +
\end{align*}</cmath>
 +
Notice that <math>f(n)=n</math> whenever <math>n</math> is an odd multiple of <math>3</math>, and the pattern of numbers that follow will always be <math>+2</math>, <math>+3</math>, <math>+2</math>, <math>+0</math>, <math>-1</math>, <math>+0</math>.
 
The largest odd multiple of <math>3</math> smaller than <math>2018</math> is <math>2013</math>, so we have
 
The largest odd multiple of <math>3</math> smaller than <math>2018</math> is <math>2013</math>, so we have
<cmath>f(2013)=2013</cmath>
+
<cmath>\begin{align*}
<cmath>f(2014)=2016</cmath>
+
f(2013)&=2013 \\
<cmath>f(2015)=2018</cmath>
+
f(2014)&=2016 \\
<cmath>f(2016)=2018</cmath>
+
f(2015)&=2018 \\
<cmath>f(2017)=2017</cmath>
+
f(2016)&=2018 \\
<cmath>f(2018)=\boxed{(B) 2017}.</cmath>
+
f(2017)&=2017 \\
 +
f(2018)&=\boxed{\textbf{(B) } 2017}.
 +
\end{align*}</cmath>
 +
minor edits by bunny1
 +
 
 +
==Solution 5 (Bash)==
 +
Writing out the first few values, we get
 +
<cmath>1,1,3,6,8,8,7,7,9,12,14,14,13,13,15,18,20,20,19,19,\ldots.</cmath> We see that every number <math>x</math> where <math>x \equiv 1\pmod 6</math> has <math>f(x)=x,f(x+1)=f(x)=x,</math> and <math>f(x-1)=f(x-2)=x+1.</math> The greatest number that's <math>1\pmod{6}</math> and less <math>2018</math> is <math>2017,</math> so we have <math>f(2017)=f(2018)=\boxed{\textbf{(B) } 2017}.</math>
 +
 
 +
==Video Solution==
  
==Solution 3 (Bashy Pattern Finding)==
+
https://www.youtube.com/watch?v=aubDsjVFFTc
Writing out the first few values, we get:
 
<math>1,1,3,6,8,8,7,7,9,12,14,14,13,13,15,18,20,20,19,19...</math>. Examining, we see that every number <math>x</math> where <math>x \equiv 1 \pmod 6</math> has <math>f(x)=x</math>, <math>f(x+1)=f(x)=x</math>, and <math>f(x-1)=f(x-2)=x+1</math>. The greatest number that's 1 (mod 6) and less <math>2018</math> is <math>2017</math>, so we have <math>f(2017)=f(2018)=2017.</math> <math>\boxed B</math>
 
  
 +
~bunny1
  
==Solution 4 (Algebra)==
+
https://youtu.be/ub6CdxulWfc
<cmath>f(n)=f(n-1)-f(n-2)+n.</cmath>
 
<cmath>f(n-1)=f(n-2)-f(n-3)+n-1.</cmath>
 
Adding the two equations, we have that <cmath>f(n)=2n-1-f(n-3).</cmath>
 
Hence, <math>f(n)+f(n-3)=2n-1</math>.
 
After plugging in <math>n-3</math> to the equation above and doing some algebra, we have that <math>f(n)-f(n-6)=6</math>.
 
We have that:
 
<cmath>f(2018)-f(2012)=6</cmath>
 
<cmath>f(2012)-f(2006)=6</cmath>
 
<cmath>\ldots</cmath>
 
<cmath>f(8)-f(2)=6</cmath>
 
Adding these <math>336</math> equations up, we have that <math>f(2018)-f(2)=6*336</math> and <math>f(2018)=\boxed{2017}</math>.
 
  
~AopsUser101
+
~savannahsolver
  
 
==See Also==
 
==See Also==

Revision as of 10:16, 14 October 2021

The following problem is from both the 2018 AMC 12B #18 and 2018 AMC 10B #20, so both problems redirect to this page.

Problem

A function $f$ is defined recursively by $f(1)=f(2)=1$ and \[f(n)=f(n-1)-f(n-2)+n\]for all integers $n \geq 3$. What is $f(2018)$?

$\textbf{(A) } 2016 \qquad \textbf{(B) } 2017 \qquad \textbf{(C) } 2018 \qquad \textbf{(D) } 2019 \qquad \textbf{(E) } 2020$

Solution 1 (Algebra)

For all integers $n \geq 7,$ note that \begin{align*} f(n)&=f(n-1)-f(n-2)+n \\ &=[f(n-2)-f(n-3)+n-1]-f(n-2)+n \\ &=-f(n-3)+2n-1 \\ &=-[f(n-4)-f(n-5)+n-3]+2n-1 \\ &=-f(n-4)+f(n-5)+n+2 \\ &=-[f(n-5)-f(n-6)+n-4]+f(n-5)+n+2 \\ &=f(n-6)+6. \end{align*} It follows that \begin{align*} f(2018)&=f(2012)+6 \\ &=f(2006)+12 \\ &=f(2000)+18 \\ & \ \vdots \\ &=f(2)+2016 \\ &=\boxed{\textbf{(B) } 2017}. \end{align*} ~MRENTHUSIASM

Solution 2 (Algebra)

For all integers $n\geq3,$ we rearrange the given equation: \[f(n)-f(n-1)+f(n-2)=n. \hspace{28.25mm}(1)\] For all integers $n\geq4,$ it follows that \[f(n-1)-f(n-2)+f(n-3)=n-1. \hspace{15mm}(2)\] For all integers $n\geq4,$ we add $(1)$ and $(2):$ \[f(n)+f(n-3)=2n-1. \hspace{38.625mm}(3)\] For all integers $n\geq7,$ it follows that \[f(n-3)+f(n-6)=2n-7. \hspace{32mm}(4)\] For all integers $n\geq7,$ we subtract $(4)$ from $(3):$ \[f(n)-f(n-6)=6. \hspace{47.5mm}(5)\] From $(5),$ we have the following system of $336$ equations: \begin{align*} f(2018)-f(2012)&=6, \\ f(2012)-f(2006)&=6, \\ f(2006)-f(2000)&=6, \\ & \ \vdots \\ f(8)-f(2)&=6. \end{align*} We add these equations up to get \[f(2018)-f(2)=6\cdot336=2016,\] from which $f(2018)=f(2)+2016=\boxed{\textbf{(B) } 2017}.$

~AopsUser101 ~MRENTHUSIASM

Solution 3 (Finite Differences)

Preamble: In this solution, we define the sequence $A$ to satisfy $a_n = f(n),$ where $a_n$ represents the $n$th term of the sequence $A.$ This solution will show a few different perspectives. Even though it may not be as quick as some of the solutions above, I feel like it is an interesting concept, and may be more motivated.

To begin, we consider the sequence $B$ formed when we take the difference of consecutive terms between $A.$ Define $b_n = a_{n+1} - a_n.$ Notice that for $n \ge 4,$ we have

$\begin{cases}\begin{aligned} a_{n+1} &= a_{n} - a_{n-1} + (n+1) \\ a_{n} &= a_{n-1} - a_{n-2} + n \end{aligned}.\end{cases}$

Notice that subtracting the second equation from the first, we see that $b_{n} = b_{n-1} - b_{n-2} + 1.$

If you didn’t notice that $B$ repeated directly in the solution above, you could also, possibly more naturally, take the finite differences of the sequence $b_n$ so that you could define $c_n = b_{n+1} - b_n.$ Using a similar method as above through reindexing and then subtracting, you could find that $c_n = c_{n-1} - c_{n-2}.$ The sum of any six consecutive terms of a sequence which satisfies such a recursion is $0,$ in which you have that $b_{n} = b_{n+6}.$ In the case in which finite differences didn’t reduce to such a special recursion, you could still find the first few terms of $C$ to see if there are any patterns, now that you have a much simpler sequence. Doing so in this case, it can also be seen by seeing that the sequence $C$ looks like \[\underbrace{2, 1, -1, -2, -1, 1,}_{\text{cycle period}} 2, 1, -1, -2, -1, 1, \ldots\] in which the same result follows.

Using the fact that $B$ repeats every six terms, this motivates us to look at the sequence $B$ more carefully. Doing so, we see that $B$ looks like \[\underbrace{2, 3, 2, 0, -1, 0,}_{\text{cycle period}} 2, 3, 2, 0, -1, 0, \ldots\] (If you tried pattern finding on sequence $B$ directly, you could also arrive at this result, although I figured defining a second sequence based on finite differences was more motivated.)

Now, there are two ways to finish.

Finish Method #1: Notice that any six consecutive terms of $B$ sum to $6,$ after which we see that $a_n = a_{n-6} + 6.$ Therefore, $a_{2018} = a_{2012} + 6 = \cdots = a_{2} + 2016 = \boxed{\textbf{(B) } 2017}.$

Finish Method #2: Notice that $a_{2018} = a_{2017} - a_{2016} + 2018 = B_{2016} + 2018 = -1 + 2018 = \boxed{\textbf{(B) } 2017}.$

~Professor-Mom

Solution 4 (Bash)

Start out by listing some terms of the sequence. \begin{align*} f(1)&=1 \\ f(2)&=1 \\ f(3)&=3 \\ f(4)&=6 \\ f(5)&=8 \\ f(6)&=8 \\  f(7)&=7 \\ f(8)&=7 \\ f(9)&=9 \\ f(10)&=12 \\ f(11)&=14 \\ f(12)&=14 \\ f(13)&=13 \\ f(14)&=13 \\ f(15)&=15 \\ & \ \vdots \end{align*} Notice that $f(n)=n$ whenever $n$ is an odd multiple of $3$, and the pattern of numbers that follow will always be $+2$, $+3$, $+2$, $+0$, $-1$, $+0$. The largest odd multiple of $3$ smaller than $2018$ is $2013$, so we have \begin{align*} f(2013)&=2013 \\ f(2014)&=2016 \\ f(2015)&=2018 \\ f(2016)&=2018 \\ f(2017)&=2017 \\ f(2018)&=\boxed{\textbf{(B) } 2017}. \end{align*} minor edits by bunny1

Solution 5 (Bash)

Writing out the first few values, we get \[1,1,3,6,8,8,7,7,9,12,14,14,13,13,15,18,20,20,19,19,\ldots.\] We see that every number $x$ where $x \equiv 1\pmod 6$ has $f(x)=x,f(x+1)=f(x)=x,$ and $f(x-1)=f(x-2)=x+1.$ The greatest number that's $1\pmod{6}$ and less $2018$ is $2017,$ so we have $f(2017)=f(2018)=\boxed{\textbf{(B) } 2017}.$

Video Solution

https://www.youtube.com/watch?v=aubDsjVFFTc

~bunny1

https://youtu.be/ub6CdxulWfc

~savannahsolver

See Also

2018 AMC 10B (ProblemsAnswer KeyResources)
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 10 Problems and Solutions
2018 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 17
Followed by
Problem 19
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. AMC logo.png