text: # 2021 AIME II Problems/Problem 15
  
  ## 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 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.
  
  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), 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 (Four Variables)
  
  We consider $f(n)$ and $g(n)$ separately:
  
  • $\boldsymbol{f(n)}$
  
  We restrict $n$ in which $k^2 for some positive integer $k,$ or $$n=(k+1)^2-p\hspace{40mm}(1)$$ for some integer $p$ such that $0\leq p<2k+1.$ By recursion, 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{19mm}(2) \\ \end{align*}
  
  • $\boldsymbol{g(n)}$
  
  If $n$ and $(k+1)^2$ have the same parity, then starting from $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.
  
  It follows that $k^2 or $$n=(k+2)^2-2q\hspace{38.25mm}(3)$$ for some integer $q$ such that $0 By recursion, 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{15.5mm}(4) \\ \end{align*}
  
  By $(2)$ and $(4),$ we have $$\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{27mm}(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}. \hspace{41.25mm}(6)$$ We substitute $(6)$ 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. \hspace{29mm}(7) \end{align*} Since $\gcd(11,10)=1,$ we know that $p-1$ must be divisible by $10,$ and $q$ must be divisible by $11.$
  
  Recall that the restrictions on $(1)$ and $(2)$ are $0\leq p<2k+1$ and $0 respectively. Substituting $(6)$ into either inequality gives $p+1 Combining all these results produces $$0 To minimize $n$ in either $(1)$ or $(3),$ we minimize $k,$ so we minimize $p$ and $q$ in $(8).$ From $(6)$ and $(7),$ we construct the following table: $\[\begin{array}{c|c|c|c} & & & \\ [-2.5ex] \boldsymbol{p} & \boldsymbol{q} & \boldsymbol{k} & \textbf{Satisfies }\boldsymbol{(8)?} \\ [0.5ex] \hline & & & \\ [-2ex] 11 & 11 & 4 & \\ 21 & 22 & 10 & \\ 31 & 33 & 16 & \checkmark \\ \geq41 & \geq44 & \geq22 & \checkmark \\ \end{array}$$ Finally, we have $(p,q,k)=(31,33,16).$ Substituting this result into either $(1)$ or $(3)$ generates $n=\boxed{258}.$
  
  • Remark
  
  We can verify that $$\frac{f(258)}{g(258)}=\frac{1\cdot31+f(258+1\cdot31)}{2\cdot33+g(258+2\cdot33)}=\frac{31+\overbrace{f(289)}^{17}}{66+\underbrace{g(324)}_{18}}=\frac{48}{84}=\frac47.$$
  
  ~MRENTHUSIASM
  
  ## Solution 3
  
  Since $n$ isn't a perfect square, let $n=m^2+k$ with $0. If $m$ is odd, then $f(n)=g(n)$. If $m$ is even, $$f(n)=(m+1)^2-(m^2+k)+(m+1)=3m+2-k$$ $$g(n)=(m+2)^2-(m^2+k)+(m+2)=5m+6-k$$ $$7(3m+2-k)=4(5m+6-k)$$ $$m=3k+10$$ Since $m$ is even, $k$ is even. Since $k\neq 0$, the smallest $k$ is $2$ which produces the smallest $n$. $k=2 \implies m=16 \implies n=16^2+2=\boxed{258}$
  
  ~Afo
explanation: The document contains a math problem from the 2021 AIME II competition, specifically Problem 15. It includes the problem statement and three different solutions to the problem. Each solution provides a detailed step-by-step approach to finding the least positive integer \( n \) such that \( \frac{f(n)}{g(n)} = \frac{4}{7} \). The final answer provided in all solutions is \( \boxed{258} \).
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 2021 AIME II Problems/Problem 15
  
  ## 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 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.
  
  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), 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 (Four Variables)
  
  We consider $f(n)$ and $g(n)$ separately:
  
  • $\boldsymbol{f(n)}$
  
  We restrict $n$ in which $k^2 for some positive integer $k,$ or $$n=(k+1)^2-p\hspace{40mm}(1)$$ for some integer $p$ such that $0\leq p<2k+1.$ By recursion, 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{19mm}(2) \\ \end{align*}
  
  • $\boldsymbol{g(n)}$
  
  If $n$ and $(k+1)^2$ have the same parity, then starting from $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.
  
  It follows that $k^2 or $$n=(k+2)^2-2q\hspace{38.25mm}(3)$$ for some integer $q$ such that $0 By recursion, 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{15.5mm}(4) \\ \end{align*}
  
  By $(2)$ and $(4),$ we have $$\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{27mm}(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}. \hspace{41.25mm}(6)$$ We substitute $(6)$ 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. \hspace{29mm}(7) \end{align*} Since $\gcd(11,10)=1,$ we know that $p-1$ must be divisible by $10,$ and $q$ must be divisible by $11.$
  
  Recall that the restrictions on $(1)$ and $(2)$ are $0\leq p<2k+1$ and $0 respectively. Substituting $(6)$ into either inequality gives $p+1 Combining all these results produces $$0 To minimize $n$ in either $(1)$ or $(3),$ we minimize $k,$ so we minimize $p$ and $q$ in $(8).$ From $(6)$ and $(7),$ we construct the following table: $\[\begin{array}{c|c|c|c} & & & \\ [-2.5ex] \boldsymbol{p} & \boldsymbol{q} & \boldsymbol{k} & \textbf{Satisfies }\boldsymbol{(8)?} \\ [0.5ex] \hline & & & \\ [-2ex] 11 & 11 & 4 & \\ 21 & 22 & 10 & \\ 31 & 33 & 16 & \checkmark \\ \geq41 & \geq44 & \geq22 & \checkmark \\ \end{array}$$ Finally, we have $(p,q,k)=(31,33,16).$ Substituting this result into either $(1)$ or $(3)$ generates $n=\boxed{258}.$
  
  • Remark
  
  We can verify that $$\frac{f(258)}{g(258)}=\frac{1\cdot31+f(258+1\cdot31)}{2\cdot33+g(258+2\cdot33)}=\frac{31+\overbrace{f(289)}^{17}}{66+\underbrace{g(324)}_{18}}=\frac{48}{84}=\frac47.$$
  
  ~MRENTHUSIASM
  
  ## Solution 3
  
  Since $n$ isn't a perfect square, let $n=m^2+k$ with $0. If $m$ is odd, then $f(n)=g(n)$. If $m$ is even, $$f(n)=(m+1)^2-(m^2+k)+(m+1)=3m+2-k$$ $$g(n)=(m+2)^2-(m^2+k)+(m+2)=5m+6-k$$ $$7(3m+2-k)=4(5m+6-k)$$ $$m=3k+10$$ Since $m$ is even, $k$ is even. Since $k\neq 0$, the smallest $k$ is $2$ which produces the smallest $n$. $k=2 \implies m=16 \implies n=16^2+2=\boxed{258}$
  
  ~Afo
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document contains a math problem from the 2021 AIME II competition, specifically Problem 15. It includes the problem statement and three different solutions to the problem. Each solution provides a detailed step-by-step approach to finding the least positive integer \( n \) such that \( \frac{f(n)}{g(n)} = \frac{4}{7} \). The final answer provided in all solutions is \( \boxed{258} \).
  
  Label: question-and-answer