Difference between revisions of "1988 AIME Problems/Problem 8"
(→Solution) |
MRENTHUSIASM (talk | contribs) m (→Solution 2 (Algebra)) |
||
(15 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The | + | The function <math>f</math>, defined on the set of ordered pairs of positive integers, satisfies the following properties: |
− | <cmath> | + | <cmath> f(x, x) = x,\; f(x, y) = f(y, x), {\rm \ and\ } (x+y)f(x, y) = yf(x, x+y). </cmath> |
− | |||
− | f(x,y) | ||
− | (x + y) f(x,y) | ||
− | </cmath> | ||
Calculate <math>f(14,52)</math>. | Calculate <math>f(14,52)</math>. | ||
− | == Solution == | + | == Solution 1 (Algebra) == |
+ | Let <math>z = x+y</math>. By the substitution <math>z=x+y,</math> we rewrite the third property in terms of <math>x</math> and <math>z,</math> then solve for <math>f(x,z):</math> | ||
+ | <cmath>\begin{align*} | ||
+ | zf(x,z-x) &= (z-x)f(x,z) \\ | ||
+ | f(x,z) &= \frac{z}{z-x} \cdot f(x,z-x). | ||
+ | \end{align*}</cmath> | ||
+ | Using the properties of <math>f,</math> we have | ||
+ | <cmath>\begin{align*} | ||
+ | f(14,52) &= \frac{52}{38} \cdot f(14,38) \\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot f(14,24) \\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot f(14,10)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot f(10,14)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot f(10,4)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot f(4,10)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot \frac{10}{6} \cdot f(4,6)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot \frac{10}{6} \cdot \frac{6}{2} \cdot f(4,2)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot \frac{10}{6} \cdot \frac{6}{2} \cdot f(2,4)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot \frac{10}{6} \cdot \frac{6}{2} \cdot \frac{4}{2} \cdot f(2,2)\\ | ||
+ | &= \frac{52}{38} \cdot \frac{38}{24} \cdot \frac{24}{10} \cdot \frac{14}{4} \cdot \frac{10}{6} \cdot \frac{6}{2} \cdot \frac{4}{2} \cdot 2\\ | ||
+ | &=\boxed{364}. | ||
+ | \end{align*}</cmath> | ||
+ | ~MRENTHUSIASM (credit given to AoPS) | ||
+ | |||
+ | == Solution 2 (Algebra)== | ||
Since all of the function's properties contain a recursive definition except for the first one, we know that <math>f(x,x) = x</math> in order to obtain an integer answer. So, we have to transform <math>f(14,52)</math> to this form by exploiting the other properties. The second one doesn't help us immediately, so we will use the third one. | Since all of the function's properties contain a recursive definition except for the first one, we know that <math>f(x,x) = x</math> in order to obtain an integer answer. So, we have to transform <math>f(14,52)</math> to this form by exploiting the other properties. The second one doesn't help us immediately, so we will use the third one. | ||
− | Note that | + | Note that <cmath>f(14,52) = f(14,14 + 38) = \frac{52}{38}\cdot f(14,38).</cmath> |
− | |||
− | <cmath>f(14,52) = f(14,14 + 38) = \frac {52}{38}f(14,38)</cmath> | ||
Repeating the process several times, | Repeating the process several times, | ||
− | <cmath> | + | <cmath>\begin{align*} |
− | \begin{ | + | f(14,52) & = f(14,14 + 38) \\ |
− | & = | + | & = \frac{52}{38}\cdot f(14,38) \\ |
− | & = | + | & = \frac{52}{38}\cdot \frac{38}{24}\cdot f(14,14 + 24) \\ |
− | & = | + | & = \frac{52}{24}\cdot f(14,24) \\ |
− | & = | + | & = \frac{52}{10}\cdot f(10,14) \\ |
− | & = | + | & = \frac{52}{10}\cdot \frac{14}{4}\cdot f(10,4) \\ |
− | & = | + | & = \frac{91}{5}\cdot f(4,10) \\ |
− | + | & = \frac{91}{3}\cdot f(4,6) \\ | |
− | + | & = 91\cdot f(2,4) \\ | |
− | + | & = 91\cdot 2 \cdot f(2,2) \\ | |
− | + | & = \boxed{364}. | |
− | + | \end{align*}</cmath> | |
− | |||
− | + | ==Solution 3 (Number Theory)== | |
+ | Notice that <math>f(x,y) = \mathrm{lcm}(x,y)</math> satisfies all three properties: | ||
− | <math> | + | For the first two properties, it is clear that <math>\mathrm{lcm}(x,x) = x</math> and <math>\mathrm{lcm}(x,y) = \mathrm{lcm}(y,x)</math>. |
− | Hence, <math>f(x,y) = \ | + | For the third property, using the identities <math>\gcd(x,y) \cdot \mathrm{lcm}(x,y) = x\cdot y</math> and <math>\gcd(x,x+y) = \gcd(x,y)</math> gives |
+ | <cmath>\begin{align*} | ||
+ | y \cdot \mathrm{lcm}(x,x+y) &= \dfrac{y \cdot x(x+y)}{\gcd(x,x+y)} \\ | ||
+ | &= \dfrac{(x+y) \cdot xy}{\gcd(x,y)} \\ | ||
+ | &= (x+y) \cdot \mathrm{lcm}(x,y). | ||
+ | \end{align*}</cmath> | ||
+ | Hence, <math>f(x,y) = \mathrm{lcm}(x,y)</math> is a solution to the functional equation. | ||
− | Since this is an | + | Since this is an AIME problem, there is exactly one correct answer, and thus, exactly one possible value of <math>f(14,52)</math>. |
− | Therefore, < | + | Therefore, we have |
+ | <cmath>\begin{align*} | ||
+ | f(14,52) &= \mathrm{lcm}(14,52) \\ | ||
+ | &= \mathrm{lcm}(2 \cdot 7,2^2 \cdot 13) \\ | ||
+ | &= 2^2 \cdot 7 \cdot 13 \\ | ||
+ | &= \boxed{364}. | ||
+ | \end{align*}</cmath> | ||
== See also == | == See also == |
Latest revision as of 13:24, 12 October 2021
Contents
Problem
The function , defined on the set of ordered pairs of positive integers, satisfies the following properties:
Calculate
.
Solution 1 (Algebra)
Let . By the substitution
we rewrite the third property in terms of
and
then solve for
Using the properties of
we have
~MRENTHUSIASM (credit given to AoPS)
Solution 2 (Algebra)
Since all of the function's properties contain a recursive definition except for the first one, we know that in order to obtain an integer answer. So, we have to transform
to this form by exploiting the other properties. The second one doesn't help us immediately, so we will use the third one.
Note that
Repeating the process several times,
Solution 3 (Number Theory)
Notice that satisfies all three properties:
For the first two properties, it is clear that and
.
For the third property, using the identities and
gives
Hence,
is a solution to the functional equation.
Since this is an AIME problem, there is exactly one correct answer, and thus, exactly one possible value of .
Therefore, we have
See also
1988 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.