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

Latest revision as of 21:31, 6 October 2024

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

Note that we should also be suspicious if our answer is $1001$ - it is a $4$ -digit number, and we were not asked to, say, divide our number by $13$ .

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 its 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

Solution 4 (really a solution, DO THIS ON A REAL TEST)

Open up a coding IDE and use recursion to do this problem. The idea is to define a function (I called it $f$ , you can call it whatever you want) with parameter $n$ (or 84 in this case) and say if $n$ is greater than 1000, then return $n-3$ . Else, return $f(f(n + 5))$ . If this doesn't make sense, then search 'Recursion' on YouTube and try to understand recursive functions. Python code:

   def f(n):
       if n >= 1000:
           return n - 3
       else:
           return f(f(n + 5))
   print(f(84))

-NL008

Or [python]def f(n):

  if n < 1000:
       return f(f(n + 5))
  else:
      return n-3

print(f(84))[/python]

-Sernegeti22

@@ Line 14: / Line 14: @@
 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>
+Note that we should also be suspicious if our answer is <math>1001</math>- it is a <math>4</math>-digit number, and we were not asked to, say, divide our number by <math>13</math>.
 == Solution 2==
@@ Line 23: / Line 25: @@
 <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.)
+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 its 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>.
+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 4 (really a solution, DO THIS ON A REAL TEST) ==
+Open up a coding IDE and use recursion to do this problem. The idea is to define a function (I called it <math>f</math>, you can call it whatever you want) with parameter <math>n</math> (or 84 in this case) and say if <math>n</math> is greater than 1000, then return <math>n-3</math>. Else, return <math>f(f(n + 5))</math>. If this doesn't make sense, then search 'Recursion' on YouTube and try to understand recursive functions. Python code:
+    def f(n):
+        if n >= 1000:
+            return n - 3
+        else:
+            return f(f(n + 5))
+    print(f(84))
+-NL008
+Or [python]def f(n):
+   if n < 1000:
+        return f(f(n + 5))
+   else:
+       return n-3
+print(f(84))[/python]
+-Sernegeti22
 == See also ==

1984 AIME (Problems • Answer Key • Resources)
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

Page

Toolbox

Search