Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 AIME II Problems/Problem 15"

(→‎Problem)
(→‎Solution)
Line 9: Line 9:
  
 
==Solution==
 
==Solution==
−
We can't have a solution without a problem.
+
 
 +
Consider what happens when we try to calculate <math>f(n)</math> where n is not a square. If <math>k^2<n<(k+1)^2</math> for (positive) integer k, recursively calculating the value of the function gives us <math>f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n</math>. Note that this formula also returns the correct value when <math>n=(k+1)^2</math>, but not when <math>n=k^2</math>. Thus <math>f(n)=k^2+3k+2-n</math> for <math>k^2<n \leq (k+1)^2</math>.
 +
 
 +
If <math>2 \mid (k+1)^2-n</math>, <math>g(n)</math> returns the same value as <math>f(n)</math>. This is because the recursion once again stops at <math>(k+1)^2</math>. We seek a case in which <math>f(n)<g(n)</math>, so obviously this is not what we want. We want <math>(k+1)^2,n</math> to have a different parity, or <math>n, k</math> have the same parity. When this is the case, <math>g(n)</math> instead returns <math>(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n</math>.
 +
 
 +
Write <math>7f(n)=4g(n)</math>, which simplifies to <math>3k^2+k-10=3n</math>. Notice that we want the <math>LHS</math> expression to be divisible by 3; as a result, <math>k \equiv 1 \pmod{3}</math>. We also want n to be strictly greater than <math>k^2</math>, so <math>k-10>0, k>10</math>. The LHS expression is always even (why?), so to ensure that k and n share the same parity, k should be even. Then the least k that satisfies these requirements is <math>k=16</math>, giving <math>n=258</math>.
 +
 
 +
Indeed, <math>f(258)=48, g(258)=84</math>, so we're done.
  
 
==See also==
 
==See also==
 
{{AIME box|year=2021|n=II|num-b=14|after=Last Question}}
 
{{AIME box|year=2021|n=II|num-b=14|after=Last Question}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 15:19, 22 March 2021

Problem

Let $f(n)$ and $g(n)$ be functions satisfying \[f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 1 + f(n+1) & \text{ otherwise} \end{cases}\]and \[g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 2 + g(n+2) & \text{ otherwise} \end{cases}\]for positive integers $n$. Find the least positive integer $n$ such that $\tfrac{f(n)}{g(n)} = \tfrac{4}{7}$.

Solution

Consider what happens when we try to calculate $f(n)$ where n is not a square. If $k^2<n<(k+1)^2$ for (positive) integer k, recursively calculating the value of the function gives us $f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n$. Note that this formula also returns the correct value when $n=(k+1)^2$, but not when $n=k^2$. Thus $f(n)=k^2+3k+2-n$ for $k^2<n \leq (k+1)^2$.

If $2 \mid (k+1)^2-n$, $g(n)$ returns the same value as $f(n)$. This is because the recursion once again stops at $(k+1)^2$. We seek a case in which $f(n)<g(n)$, so obviously this is not what we want. We want $(k+1)^2,n$ to have a different parity, or $n, k$ have the same parity. When this is the case, $g(n)$ instead returns $(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n$.

Write $7f(n)=4g(n)$, which simplifies to $3k^2+k-10=3n$. Notice that we want the $LHS$ expression to be divisible by 3; as a result, $k \equiv 1 \pmod{3}$. We also want n to be strictly greater than $k^2$, so $k-10>0, k>10$. The LHS expression is always even (why?), so to ensure that k and n share the same parity, k should be even. Then the least k that satisfies these requirements is $k=16$, giving $n=258$.

Indeed, $f(258)=48, g(258)=84$, so we're done.

See also

2021 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last Question
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_15&oldid=149723"