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

Revision as of 04:00, 12 May 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 1

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 - if we check our answer, it works. Therefore, the answer is $\boxed{258}$ .

-Ross Gao

Solution 2 (More Variables)

We restrict $n$ in which $k^2<n\leq(k+1)^2$ for some positive integer $k,$ or $n=(k+1)^2-p\hspace{15mm}(1)$ for some nonnegative integer $p.$ By observations, we get $\begin{align*} f\left((k+1)^2\right)&=k+1, \\ f\left((k+1)^2-1\right)&=k+2, \\ f\left((k+1)^2-2\right)&=k+3, \\ &\cdots \\ f\bigl(\phantom{ }\underbrace{(k+1)^2-p}_{n}\phantom{ }\bigr)&=k+p+1. \hspace{15mm}(2) \\ \end{align*}$ If $n$ and $(k+1)^2$ have the same parity, then starting with $g\left((k+1)^2\right)=k+1,$ we get $g(n)=f(n)$ by a similar process. This contradicts the precondition $\frac{f(n)}{g(n)} = \frac{4}{7}.$ Therefore, $n$ and $(k+1)^2$ must have different parities, from which $n$ and $(k+2)^2$ must have the same parity.

Along with the earlier restriction, note that $k^2<n\leq(k+1)^2<(k+2)^2,$ or $n=(k+2)^2-2q\hspace{15mm}(3)$ for some positive integer $q.$ By observations, we get $\begin{align*} g\left((k+2)^2\right)&=k+2, \\ g\left((k+2)^2-2\right)&=k+4, \\ g\left((k+2)^2-4\right)&=k+6, \\ &\cdots \\ g\bigl(\phantom{ }\underbrace{(k+2)^2-2q}_{n}\phantom{ }\bigr)&=k+2q+2. \hspace{15mm}(4) \\ \end{align*}$ Together, we have $\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{15mm}(5)$ From $(1)$ and $(3),$ equating the expressions for $n$ gives $(k+1)^2-p=(k+2)^2-2q.$ Solving for $k$ produces $k=\frac{2q-p-3}{2}.$ We substitute this into $(5),$ then simplify, cross-multiply, and rearrange: $\begin{align*} \frac{\tfrac{2q-p-3}{2}+p+1}{\tfrac{2q-p-3}{2}+2q+2}&=\frac{4}{7} \\ \frac{p+2q-1}{-p+6q+1}&=\frac{4}{7} \\ 7p+14q-7&=-4p+24q+4 \\ 11p-11&=10q \\ 11(p-1)&=10q. \end{align*}$

SOLUTION IN PROGRESS. NO EDIT PLEASE--A MILLION THANKS.

Remark

We can verify that $\frac{f(258)}{g(258)}=\frac{31+\overbrace{f(289)}^{17}}{2\cdot33+\underbrace{f(324)}_{18}}=\frac{48}{84}=\frac47.$

~MRENTHUSIASM

Video Solution

https://youtu.be/tRVe2bKwIY8

@@ Line 31: / Line 31: @@
 If <math>n</math> and <math>(k+1)^2</math> have the same parity, then starting with <math>g\left((k+1)^2\right)=k+1,</math> we get <math>g(n)=f(n)</math> by a similar process. This contradicts the precondition <math>\frac{f(n)}{g(n)} = \frac{4}{7}.</math> Therefore, <math>n</math> and <math>(k+1)^2</math> must have different parities, from which <math>n</math> and <math>(k+2)^2</math> must have the same parity.
-Along with the earlier restriction, note that <math>k^2<n<(k+2)^2,</math> or <cmath>n=(k+2)^2-2q\hspace{15mm}(3)</cmath> for some positive integer <math>q.</math> By observations, we get
+Along with the earlier restriction, note that <math>k^2<n\leq(k+1)^2<(k+2)^2,</math> or <cmath>n=(k+2)^2-2q\hspace{15mm}(3)</cmath> for some positive integer <math>q.</math> By observations, we get
 <cmath>\begin{align*}
 g\left((k+2)^2\right)&=k+2, \\
@@ Line 40: / Line 40: @@
 \end{align*}</cmath>
 Together, we have <cmath>\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{15mm}(5)</cmath>
+From <math>(1)</math> and <math>(3),</math> equating the expressions for <math>n</math> gives <math>(k+1)^2-p=(k+2)^2-2q.</math> Solving for <math>k</math> produces <cmath>k=\frac{2q-p-3}{2}.</cmath>
+We substitute this into <math>(5),</math> then simplify, cross-multiply, and rearrange:
+<cmath>\begin{align*}
+\frac{\tfrac{2q-p-3}{2}+p+1}{\tfrac{2q-p-3}{2}+2q+2}&=\frac{4}{7} \\
+\frac{p+2q-1}{-p+6q+1}&=\frac{4}{7} \\
+p+14q-7&=-4p+24q+4 \\
+p-11&=10q \\
+(p-1)&=10q.
+\end{align*}</cmath>
 <b>SOLUTION IN PROGRESS. NO EDIT PLEASE--A MILLION THANKS.</b>

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

Page

Toolbox

Search