Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 AMC 10B Problems/Problem 20"
Line 101: Line 101:
  
 
==Solution 6==
 
==Solution 6==
−
<math>f(n)=f(n-1)-f(n-2)+n</math>
+
<math>f(n)=f(n-1)-f(n-2)+n</math><math>\newline</math>
−
<math>f(n-1)=f(n-2)-f(n-3)+n-1</math>
+
<math>f(n-1)=f(n-2)-f(n-3)+n-1</math><math>\newline</math>
−
Subtracting those two and rearranging gives <math>f(n)-2f(n-1)+2f(n-2)-f(n-3)=1</math>
+
Subtracting those two and rearranging gives <math>f(n)-2f(n-1)+2f(n-2)-f(n-3)=1</math><math>\newline</math>
−
<math>f(n-1)-2f(n-2)+2f(n-3)-f(n-4)=1</math>
+
<math>f(n-1)-2f(n-2)+2f(n-3)-f(n-4)=1</math><math>\newline</math>
−
Subtracting those two gives <math>f(n)-3f(n-1)+4f(n-2)-3f(n-3)+f(n-4)=0</math>
+
Subtracting those two gives <math>f(n)-3f(n-1)+4f(n-2)-3f(n-3)+f(n-4)=0</math><math>\newline</math>
−
The characteristic polynomial is <math>x^4-3x^3+4x^2-3x+1=0</math>
+
The characteristic polynomial is <math>x^4-3x^3+4x^2-3x+1=0</math><math>\newline</math>
−
<math>x=1</math> is a root, so using synthetic division results in <math>(x-1)(x^3-2x^2+2x-1)=0</math>
+
<math>x=1</math> is a root, so using synthetic division results in <math>(x-1)(x^3-2x^2+2x-1)=0</math><math>\newline</math>
−
<math>x=1</math> is a root, so using synthetic division results in <math>(x-1)^2(x^2-x+1)=0</math>
+
<math>x=1</math> is a root, so using synthetic division results in <math>(x-1)^2(x^2-x+1)=0</math><math>\newline</math>
−
<math>x^2-x+1=0</math> has roots <math>x=\frac{1}{2}\pm\frac{i\sqrt{3}}{2}</math>
+
<math>x^2-x+1=0</math> has roots <math>x=\frac{1}{2}\pm\frac{i\sqrt{3}}{2}</math><math>\newline</math>
−
And <math>f(n)=(An+D)*1^n+B*(\frac{1}{2}-\frac{i\sqrt{3}}{2})^n+C*(\frac{1}{2}+\frac{i\sqrt{3}}{2})^n</math>
+
And <math>f(n)=(An+D)*1^n+B*(\frac{1}{2}-\frac{i\sqrt{3}}{2})^n+C*(\frac{1}{2}+\frac{i\sqrt{3}}{2})^n</math><math>\newline</math>
−
Plugging in <math>n=1</math>, <math>n=2</math>, <math>n=3</math>, and <math>n=4</math> results in a system of <math>3</math> linear equations
+
Plugging in <math>n=1</math>, <math>n=2</math>, <math>n=3</math>, and <math>n=4</math> results in a system of <math>3</math> linear equations<math>\newline</math>
−
Solving them gives <math>A=1, B=\frac{1}{2}-\frac{i\sqrt{3}}{2}, C=\frac{1}{2}+\frac{i\sqrt{3}}{2}, D=1</math>
+
Solving them gives <math>A=1, B=\frac{1}{2}-\frac{i\sqrt{3}}{2}, C=\frac{1}{2}+\frac{i\sqrt{3}}{2}, D=1</math><math>\newline</math>
−
So plugging in <math>n=2018</math> results in <math>2018+1+(\frac{1}{2}-\frac{i\sqrt{3}}{2})^{2019}+(\frac{1}{2}+\frac{i\sqrt{3}}{2})^{2019}=2019+(cos(-60)+sin(-60))^{2019})+(cos(60)+sin(60))^{2019})=2019+(cos(-60*2019)+sin(-60*2019))+(cos(60*2019)+sin(60*2019))=\boxed{2017}</math>
+
So plugging in <math>n=2018</math> results in <math>2018+1+(\frac{1}{2}-\frac{i\sqrt{3}}{2})^{2019}+(\frac{1}{2}+\frac{i\sqrt{3}}{2})^{2019}=2019+(cos(-60)+sin(-60))^{2019})+(cos(60)+sin(60))^{2019})=2019+(cos(-60*2019)+sin(-60*2019))+(cos(60*2019)+sin(60*2019))=\boxed{2017}</math><math>\newline</math>
 
~ryanbear
 
~ryanbear
  

Revision as of 16:17, 23 July 2023

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 (Pattern)

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*}

Solution 5 (Pattern)

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 than $2018$ is $2017,$ so we have $f(2017)=f(2018)=\boxed{\textbf{(B) } 2017}.$

Solution 6

$f(n)=f(n-1)-f(n-2)+n$$\newline$ $f(n-1)=f(n-2)-f(n-3)+n-1$$\newline$ Subtracting those two and rearranging gives $f(n)-2f(n-1)+2f(n-2)-f(n-3)=1$$\newline$ $f(n-1)-2f(n-2)+2f(n-3)-f(n-4)=1$$\newline$ Subtracting those two gives $f(n)-3f(n-1)+4f(n-2)-3f(n-3)+f(n-4)=0$$\newline$ The characteristic polynomial is $x^4-3x^3+4x^2-3x+1=0$$\newline$ $x=1$ is a root, so using synthetic division results in $(x-1)(x^3-2x^2+2x-1)=0$$\newline$ $x=1$ is a root, so using synthetic division results in $(x-1)^2(x^2-x+1)=0$$\newline$ $x^2-x+1=0$ has roots $x=\frac{1}{2}\pm\frac{i\sqrt{3}}{2}$$\newline$ And $f(n)=(An+D)*1^n+B*(\frac{1}{2}-\frac{i\sqrt{3}}{2})^n+C*(\frac{1}{2}+\frac{i\sqrt{3}}{2})^n$$\newline$ Plugging in $n=1$, $n=2$, $n=3$, and $n=4$ results in a system of $3$ linear equations$\newline$ Solving them gives $A=1, B=\frac{1}{2}-\frac{i\sqrt{3}}{2}, C=\frac{1}{2}+\frac{i\sqrt{3}}{2}, D=1$$\newline$ So plugging in $n=2018$ results in $2018+1+(\frac{1}{2}-\frac{i\sqrt{3}}{2})^{2019}+(\frac{1}{2}+\frac{i\sqrt{3}}{2})^{2019}=2019+(cos(-60)+sin(-60))^{2019})+(cos(60)+sin(60))^{2019})=2019+(cos(-60*2019)+sin(-60*2019))+(cos(60*2019)+sin(60*2019))=\boxed{2017}$$\newline$ ~ryanbear

Video Solution

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

~bunny1

https://youtu.be/ub6CdxulWfc

~savannahsolver

See Also

2018 AMC 10B (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 10 Problems and Solutions
2018 AMC 12B (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_20&oldid=196007"