2021 AIME II Problem 15

Attempt Problem 15 of the 2021 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2021 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

15.

Let f(n)f(n) and g(n)g(n) be functions satisfying f(n)={nif n isan integer1+f(n+1)otherwise \begin{aligned} &f(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{if } \sqrt{n} \text{ is} \\ \text{an integer}} \\ 1 + f(n+1) & \text{otherwise} \end{cases} \end{aligned} and g(n)={nif n isan integer2+g(n+2)otherwise \begin{aligned} &g(n) = \\ &\quad \begin{cases} \sqrt{n} & \substack{\text{if } \sqrt{n} \text{ is} \\ \text{an integer}} \\ 2 + g(n+2) & \text{otherwise} \end{cases} \end{aligned} for positive integers n.n. Find the least positive integer nn such that f(n)g(n)=47.\frac{f(n)}{g(n)} = \frac{4}{7}.

Answer: 258
Concepts:functionperfect squareparity
Difficulty rating: 3160
Solution:

Let kk be the least integer with k2n.k^2 \ge n. The function ff climbs one step at a time to the next perfect square, so f(n)=k+(k2n).f(n) = k + (k^2 - n). The function gg climbs by 22s, preserving the parity of its argument, and j2j(mod2),j^2 \equiv j \pmod 2, so g(n)=j+(j2n)g(n) = j + (j^2 - n) where jj is the least integer with j2nj^2 \ge n and jn(mod2).j \equiv n \pmod 2. If kn(mod2)k \equiv n \pmod 2 then j=kj = k and the ratio is 1;1; so we need k≢n(mod2),k \not\equiv n \pmod 2, in which case j=k+1j = k + 1 and g(n)f(n)=(k+1)2k2+1g(n) - f(n) = (k+1)^2 - k^2 + 1 =2k+2.= 2k + 2.

Then 7f=4g=4f+4(2k+2)7f = 4g = 4f + 4(2k + 2) gives f=8(k+1)3,f = \frac{8(k+1)}{3}, so k2(mod3)k \equiv 2 \pmod 3 and n=k2+k8(k+1)3,n = k^2 + k - \frac{8(k+1)}{3}, subject to (k1)2<nk2(k-1)^2 \lt n \le k^2 and n≢k(mod2).n \not\equiv k \pmod 2.

For k=2,5,8,11k = 2, 5, 8, 11 the formula gives n=2,14,48,100,n = -2, 14, 48, 100, each failing n>(k1)2;n \gt (k-1)^2; for k=14,k = 14, n=170n = 170 is in range but has the same parity as k.k. For k=17,k = 17, n=289+1748=258,n = 289 + 17 - 48 = 258, which satisfies 256<258289256 \lt 258 \le 289 and is even while kk is odd. Indeed f(258)=17+31=48f(258) = 17 + 31 = 48 and g(258)=18+66=84,g(258) = 18 + 66 = 84, with 4884=47,\frac{48}{84} = \frac{4}{7}, so the least nn is 258.258.

← Problem 14#14
Full Exam

Problem 15 in Other Years