Question

对正整数 $n$ ，定义函数 $f(n)$ 和 $g(n)$ 如下：以及求最小正整数 $n$ ，使得 $\frac{f(n)}{g(n)} = \frac{4}{7}$ 。 $\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}$ $\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}$

Let $f(n)$ and $g(n)$ be functions satisfying $\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 $\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.$ Find the least positive integer $n$ such that $\frac{f(n)}{g(n)} = \frac{4}{7}.$

答案

答案：258

知识点：函数完全平方数奇偶性

难度评级：3160

解答：

令 $k$ 为满足 $k^2 \ge n$ 的最小整数。函数 $f$ 每次前进一步直到下一个完全平方数，所以 $f(n) = k + (k^2 - n)$ 。函数 $g$ 每次前进 $2$ 步，保持自变量的奇偶性，而 $j^2 \equiv j \pmod 2$ ，所以 $g(n) = j + (j^2 - n)$ ，其中 $j$ 是满足 $j^2 \ge n$ 且 $j \equiv n \pmod 2$ 的最小整数。若 $k \equiv n \pmod 2$ ，则 $j = k$ ，比值为 $1$ ；所以需要 $k \not\equiv n \pmod 2$ ，此时 $j = k + 1$ ，且 $g(n) - f(n) = (k+1)^2 - k^2 + 1$ $= 2k + 2$ 。

于是 $7f = 4g = 4f + 4(2k + 2)$ ，得 $f = \frac{8(k+1)}{3}$ ，所以 $k \equiv 2 \pmod 3$ ，并且还需满足 $(k-1)^2 \lt n \le k^2$ 和 $n \not\equiv k \pmod 2$ 。 $n = k^2 + k - \frac{8(k+1)}{3},$

对 $k = 2, 5, 8, 11$ ，公式分别给出 $n = -2, 14, 48, 100$ 都不满足 $n \gt (k-1)^2$ ；对 $k = 14$ ， $n = 170$ 在范围内，但与 $k$ 。奇偶性相同。对 $k = 17$ ， $n = 289 + 17 - 48 = 258$ ，满足 $256 \lt 258 \le 289$ ，且 $n$ 为偶数而 $k$ 为奇数。确实， $f(258) = 17 + 31 = 48$ ， $g(258) = 18 + 66 = 84$ ，且 $\frac{48}{84} = \frac{4}{7}$ ，所以最小的 n 是 $258$ 。

Let $k$ be the least integer with $k^2 \ge n.$ The function $f$ climbs one step at a time to the next perfect square, so $f(n) = k + (k^2 - n).$ The function $g$ climbs by $2$ s, preserving the parity of its argument, and $j^2 \equiv j \pmod 2,$ so $g(n) = j + (j^2 - n)$ where $j$ is the least integer with $j^2 \ge n$ and $j \equiv n \pmod 2.$ If $k \equiv n \pmod 2$ then $j = k$ and the ratio is $1;$ so we need $k \not\equiv n \pmod 2,$ in which case $j = k + 1$ and $g(n) - f(n) = (k+1)^2 - k^2 + 1$ $= 2k + 2.$

Then $7f = 4g = 4f + 4(2k + 2)$ gives $f = \frac{8(k+1)}{3},$ so $k \equiv 2 \pmod 3$ and $n = k^2 + k - \frac{8(k+1)}{3},$ subject to $(k-1)^2 \lt n \le k^2$ and $n \not\equiv k \pmod 2.$

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

2021 AIME II 第 15 题

答案：258

难度评级：3160

解答：

其他年份的第 15 题