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

Revision as of 00:51, 24 September 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)} \text{ 2016} \qquad \textbf{(B)} \text{ 2017} \qquad \textbf{(C)} \text{ 2018} \qquad \textbf{(D)} \text{ 2019} \qquad \textbf{(E)} \text{ 2020}$

Solution 1 (A Bit Bashy)

Start out by listing some terms of the sequence. $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$ $.....$ 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 $f(2013)=2013$ $f(2014)=2016$ $f(2015)=2018$ $f(2016)=2018$ $f(2017)=2017$ $f(2018)=\boxed{(B) 2017}.$ minor edits by bunny1

Solution 2 (Bashy Pattern Finding)

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...$ . Examining, 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)=2017.$ $\boxed B$

Solution 3 (Algebra)

$f(n)=f(n-1)-f(n-2)+n.$ $f(n-1)=f(n-2)-f(n-3)+n-1.$ Adding the two equations, we have that $f(n)=2n-1-f(n-3).$ Hence, $f(n)+f(n-3)=2n-1$ . After plugging in $n-3$ to the equation above and doing some algebra, we have that $f(n)-f(n-6)=6$ . Consequently, $f(2018)-f(2012)=6.$ $f(2012)-f(2006)=6.$ $\ldots$ $f(8)-f(2)=6.$ Adding these $336$ equations up, we have that $f(2018)-f(2)=6 \cdot 336$ and $f(2018)=\boxed{2017}$ .

~AopsUser101

Solution 4 (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.

————————————————

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} a_{n+1} = a_{n} - a_{n-1} + (n+1) \\ a_{n} = a_{n-1} - a_{n-2} + n. \end{cases}$ Notice that subtracting the second equation from the first, we see that $b_{n} = b_{n-1} - b_{n-2} + 1.$

Evaluating the first few terms of $B$ , we see that we get $\underbrace{0, 2, 3, 2, 0, -1,}_{\text{cycle}} 0, 2, 3, 2, 0, -1, \cdots,$ in which we see it has a cycle period of $6$ !

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{2017}.$

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

—————————————————

Note: 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}.$ Using the fact that $b_1 = 0, \ b_2 = 2,$ and $b_3 = 3,$ we see that the sequence $C$ looks like $2, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, 1, \cdots$ However, $C$ has a cycle period of $6$ ! Notice that any six consecutive terms of $C$ sum to $0,$ which implies that $b_n = b_{n+6}.$

~ Professor-Mom

Video Solution

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

~bunny1

https://youtu.be/ub6CdxulWfc

~savannahsolver

@@ Line 59: / Line 59: @@
 ==Solution 4 (Finite Differences)==
-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>
+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.
+————————————————
 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 <cmath>\begin{cases} a_{n+1} = a_{n} - a_{n-1} + (n+1) \\ a_{n} = a_{n-1} - a_{n-2} + n. \end{cases}</cmath> Notice that subtracting the second equation from the first, we see that <math>b_{n} = b_{n-1} - b_{n-2} + 1.</math>
-Evaluating the first few terms of <math>B</math>, we see that we get <cmath>\underbrace{0, 2, 3, 2, 0, -1,}_{\text{cycle}} 0, 2, 3, 2, 0, -1, \cdots, </cmath> in which we see it has a cycle period of <math>6</math>! 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>
+Evaluating the first few terms of <math>B</math>, we see that we get <cmath>\underbrace{0, 2, 3, 2, 0, -1,}_{\text{cycle}} 0, 2, 3, 2, 0, -1, \cdots, </cmath> in which we see it has a cycle period of <math>6</math>!
+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{2017}.</math>
-Therefore, <math>a_{2018} = a_{2012} + 6 = \cdots = a_{2} + 2016 = \boxed{2017}.</math>
+Finish Method #2: Notice that <math>a_{2018} = a_{2017} - a_{2016} + 2018 = B_{2016} + 2018 = -1 + 2018 = \boxed{2017}.</math>
 —————————————————
-Note: If you didn’t notice that <math>B</math> repeated directly in the solution above, you could also 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> Using the fact that <math>b_1 = 0, \ b_2 = 2, \ </math>and <math>b_3 = 3,</math> we see that the sequence <math>C</math> looks like <cmath>2, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, 1, \cdots</cmath> However, <math>C</math> has a cycle period of <math>6</math>! Notice that any six consecutive terms of <math>C</math> sum to <math>0,</math> which implies that <math>b_n = b_{n+6}.</math>
+Note: 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> Using the fact that <math>b_1 = 0, \ b_2 = 2, \ </math>and <math>b_3 = 3,</math> we see that the sequence <math>C</math> looks like <cmath>2, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, 1, \cdots</cmath> However, <math>C</math> has a cycle period of <math>6</math>! Notice that any six consecutive terms of <math>C</math> sum to <math>0,</math> which implies that <math>b_n = b_{n+6}.</math>
 ~ Professor-Mom

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

Page

Toolbox

Search