Difference between revisions of "1984 AIME Problems/Problem 7"

(Solution 3)
(46 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
The function f is defined on the set of integers and satisfies
+
The [[function]] f is defined on the [[set]] of [[integer]]s and satisfies <math>f(n)=\begin{cases}
<math>
+
n-3&\mbox{if}\ n\ge 1000\\
f(n)=
+
f(f(n+5))&\mbox{if}\ n<1000\end{cases}</math>
\begin{cases}
 
n-3 & \mbox{if }n\ge 1000 \\
 
f(f(n+5)) & \mbox{if }n<1000
 
\end{cases}
 
</math>
 
  
Find <math>\displaystyle f(84)</math>.
+
Find <math>f(84)</math>.
 +
 
 +
== Solution 1 ==
 +
Define <math>f^{h} = f(f(\cdots f(f(x))\cdots))</math>, where the function <math>f</math> is performed <math>h</math> times. We find that <math> f(84) = f(f(89)) = f^2(89) = f^3(94) = \ldots f^{y}(1004)</math>. <math>1004 = 84 + 5(y - 1) \Longrightarrow y = 185</math>. So we now need to reduce <math>f^{185}(1004)</math>.
 +
 
 +
Let’s write out a couple more iterations of this function:
 +
<cmath>\begin{align*}f^{185}(1004)&=f^{184}(1001)=f^{183}(998)=f^{184}(1003)=f^{183}(1000)\\
 +
&=f^{182}(997)=f^{183}(1002)=f^{182}(999)=f^{183}(1004)\end{align*}</cmath>
 +
So this function reiterates with a period of 2 for <math>x</math>. It might be tempting at first to assume that <math>f(1004) = 1001</math> is the answer; however, that is not true since the solution occurs slightly before that. Start at <math>f^3(1004)</math>:
 +
<cmath>f^{3}(1004)=f^{2}(1001)=f(998)=f^{2}(1003)=f(1000)=\boxed{997}</cmath>
 +
 
 +
== Solution 2==
 +
We start by finding values of the function right under <math>1000</math> since they require iteration of the function.
 +
 
 +
<cmath>f(999)=f(f(1004))=f(1001)=998</cmath>
 +
<cmath>f(998)=f(f(1003))=f(1000)=997</cmath>
 +
<cmath>f(997)=f(f(1002))=f(999)=998</cmath>
 +
<cmath>f(996)=f(f(1001))=f(998)=997</cmath>
 +
 
 +
Soon we realize the <math>f(k)</math> for integers <math>k<1000</math> either equal <math>998</math> or <math>997</math> based on it parity. (If short on time, a guess of <math>998</math> or <math>997</math> can be taken now.)
 +
If <math>k</math> is even <math>f(k)=997</math> if <math>k</math> is odd <math>f(k)=998</math>. <math>84</math> has even parity, so <math>f(84)=997</math>.
 +
The result may be rigorously shown through induction.
 +
 
 +
 
 +
== Solution 3 ==
 +
 
 +
Assume that <math>f(84)</math> is to be performed <math>n+1</math> times. Then we have
 +
<cmath>f(84)=f^{n+1}(84)=f(f^n(84+5))</cmath>
 +
In order to find <math>f(84)</math>, we want to know the smallest value of
 +
<cmath>f^n(84+5)\ge1000</cmath>
 +
Because then
 +
<cmath>f(84)=f(f^n(84+5))=(f^n(84+5))-3</cmath>
 +
From which we'll get a numerical value for <math>f(84)</math>.
 +
 
 +
Notice that the value of <math>n</math> we expect to find is basically the smallest <math>n</math> such that after <math>f(x)=f(f(x+5))</math> is performed <math>\frac{n}{2}</math> times and then <math>f(x)=x-3</math> is performed back <math>\frac{n}{2}</math> times, the result is greater than or equal to <math>1000</math>.
 +
 
 +
In this case, the value of <math>n</math> for <math>f(84)</math> is <math>916</math>, because
 +
<cmath>84+\frac{916}{2}\cdot5-\frac{916}{2}\cdot3=1000\Longrightarrow f^{916}(84+5))=1000</cmath>
 +
Thus
 +
<cmath>f(84)=f(f^{916}(84+5))=f(1000)=1000-3=\boxed{997}</cmath>
 +
 
 +
~ Nafer
  
== Solution ==
 
{{solution}}
 
 
== See also ==
 
== See also ==
* [[1984 AIME Problems/Problem 6 | Previous problem]]
+
{{AIME box|year=1984|num-b=6|num-a=8}}
* [[1984 AIME Problems/Problem 8 | Next problem]]
+
* [[AIME Problems and Solutions]]
* [[1984 AIME Problems]]
+
* [[American Invitational Mathematics Examination]]
 +
* [[Mathematics competition resources]]
 +
 
 +
[[Category:Intermediate Algebra Problems]]

Revision as of 19:34, 20 August 2019

Problem

The function f is defined on the set of integers and satisfies $f(n)=\begin{cases} n-3&\mbox{if}\ n\ge 1000\\ f(f(n+5))&\mbox{if}\ n<1000\end{cases}$

Find $f(84)$.

Solution 1

Define $f^{h} = f(f(\cdots f(f(x))\cdots))$, where the function $f$ is performed $h$ times. We find that $f(84) = f(f(89)) = f^2(89) = f^3(94) = \ldots f^{y}(1004)$. $1004 = 84 + 5(y - 1) \Longrightarrow y = 185$. So we now need to reduce $f^{185}(1004)$.

Let’s write out a couple more iterations of this function: \begin{align*}f^{185}(1004)&=f^{184}(1001)=f^{183}(998)=f^{184}(1003)=f^{183}(1000)\\ &=f^{182}(997)=f^{183}(1002)=f^{182}(999)=f^{183}(1004)\end{align*} So this function reiterates with a period of 2 for $x$. It might be tempting at first to assume that $f(1004) = 1001$ is the answer; however, that is not true since the solution occurs slightly before that. Start at $f^3(1004)$: \[f^{3}(1004)=f^{2}(1001)=f(998)=f^{2}(1003)=f(1000)=\boxed{997}\]

Solution 2

We start by finding values of the function right under $1000$ since they require iteration of the function.

\[f(999)=f(f(1004))=f(1001)=998\] \[f(998)=f(f(1003))=f(1000)=997\] \[f(997)=f(f(1002))=f(999)=998\] \[f(996)=f(f(1001))=f(998)=997\]

Soon we realize the $f(k)$ for integers $k<1000$ either equal $998$ or $997$ based on it parity. (If short on time, a guess of $998$ or $997$ can be taken now.) If $k$ is even $f(k)=997$ if $k$ is odd $f(k)=998$. $84$ has even parity, so $f(84)=997$. The result may be rigorously shown through induction.


Solution 3

Assume that $f(84)$ is to be performed $n+1$ times. Then we have \[f(84)=f^{n+1}(84)=f(f^n(84+5))\] In order to find $f(84)$, we want to know the smallest value of \[f^n(84+5)\ge1000\] Because then \[f(84)=f(f^n(84+5))=(f^n(84+5))-3\] From which we'll get a numerical value for $f(84)$.

Notice that the value of $n$ we expect to find is basically the smallest $n$ such that after $f(x)=f(f(x+5))$ is performed $\frac{n}{2}$ times and then $f(x)=x-3$ is performed back $\frac{n}{2}$ times, the result is greater than or equal to $1000$.

In this case, the value of $n$ for $f(84)$ is $916$, because \[84+\frac{916}{2}\cdot5-\frac{916}{2}\cdot3=1000\Longrightarrow f^{916}(84+5))=1000\] Thus \[f(84)=f(f^{916}(84+5))=f(1000)=1000-3=\boxed{997}\]

~ Nafer

See also

1984 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 6
Followed by
Problem 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions