Difference between revisions of "1984 AIME Problems/Problem 7"
(→Solution 2) |
Serengeti22 (talk | contribs) (→Solution 4 (Not really a solution, DON'T DO THIS ON A REAL TEST)) |
||
(46 intermediate revisions by 7 users not shown) | |||
Line 12: | Line 12: | ||
<cmath>\begin{align*}f^{185}(1004)&=f^{184}(1001)=f^{183}(998)=f^{184}(1003)=f^{183}(1000)\\ | <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> | &=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) = | + | 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> | <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== | == Solution 2== | ||
− | We start by finding values of the function right under 1000 since they require | + | 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> |
− | f(998)=f(f(1003))=f(1000)=997 | + | <cmath>f(998)=f(f(1003))=f(1000)=997</cmath> |
− | f(997)=f(f(1002))=f(999)=998 | + | <cmath>f(997)=f(f(1002))=f(999)=998</cmath> |
− | f(996)=f(f(1001))=f(998)=997 | + | <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 | + | 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 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 (Not really a solution, DON'T 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 == | == See also == |
Latest revision as of 17:14, 12 June 2024
Contents
Problem
The function f is defined on the set of integers and satisfies
Find .
Solution 1
Define , where the function
is performed
times. We find that
.
. So we now need to reduce
.
Let’s write out a couple more iterations of this function:
So this function reiterates with a period of 2 for
. It might be tempting at first to assume that
is the answer; however, that is not true since the solution occurs slightly before that. Start at
:
Note that we should also be suspicious if our answer is - it is a
-digit number, and we were not asked to, say, divide our number by
.
Solution 2
We start by finding values of the function right under since they require iteration of the function.
Soon we realize the for integers
either equal
or
based on its parity. (If short on time, a guess of
or
can be taken now.)
If
is even,
. If
is odd,
.
has even parity, so
.
The result may be rigorously shown through induction.
Solution 3
Assume that is to be performed
times. Then we have
In order to find
, we want to know the smallest value of
Because then
From which we'll get a numerical value for
.
Notice that the value of we expect to find is basically the smallest
such that after
is performed
times and then
is performed back
times, the result is greater than or equal to
.
In this case, the value of for
is
, because
Thus
~ Nafer
Solution 4 (Not really a solution, DON'T 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 , you can call it whatever you want) with parameter
(or 84 in this case) and say if
is greater than 1000, then return
. Else, return
. 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 |