Question

对每个正整数 $n$ ，令 $f(n) = \sum_{k=1}^{100} \lfloor \log_{10}(kn) \rfloor$ 。求最大的 $n$ ，使其满足 $f(n) \le 300$ 。

注： $\lfloor x \rfloor$ 是小于或等于 $x$ 的最大整数。

For each positive integer $n,$ let $f(n) = \sum_{k=1}^{100} \lfloor \log_{10}(kn) \rfloor.$ Find the largest value of $n$ for which $f(n) \le 300.$

Note: $\lfloor x \rfloor$ is the greatest integer less than or equal to $x.$

答案

答案：109

知识点：取整函数对数数字

难度评级：3060

小提示：

每项 $\lfloor \log_{10}(kn) \rfloor$ 都随 $n$ 的增大而不减，所以 $f$ 单调不减；先计算基准值 $f(100) = 292$

Each term $\lfloor \log_{10}(kn) \rfloor$ never decreases as $n$ grows, so $f$ is nondecreasing; compute $f(100) = 292$ as a baseline

大提示：

当 $n$ 略大于 $100$ 时，数出有多少个 $k$ 满足 $kn \ge 1000$ ，再数出有多少个 $k$ 满足 $kn \ge 10000$ ，就能看出 $f(n)$ 何时达到 $300$

For $n$ slightly above $100,$ count the $k$ with $kn \ge 1000$ and the $k$ with $kn \ge 10000$ to see exactly when $f(n)$ reaches $300$

解答：

每项 $\lfloor \log_{10}(kn) \rfloor$ 随 $n$ 单调不减，所以 $f$ 单调不减，我们只需确定它何时超过 $300$ 。当 $n = 100$ 时，乘积 $kn$ 从 $100$ 到 $10^4$ ，于是 $\lfloor \log_{10} \rfloor = 2$ 对应 $k \le 9$ ， $3$ 对应 $10 \le k \le 99$ ， $4$ 对应 $k = 100$ ，所以 $f(100) = 9 \cdot 2 + 90 \cdot 3$ $+ 4 = 292$ 。

对 $n = 109$ ，因为 $9 \cdot 109 = 981 \lt 1000$ ，且 $91 \cdot 109 = 9919 \lt 10^4$ ，各项分别为 $2$ （ $k \le 9$ ）、 $3$ （ $10 \le k \le 91$ ）和 $4$ （ $92 \le k \le 100$ ）： $\begin{aligned} f(109) &= 9 \cdot 2 + 82 \cdot 3 \\ &\quad {}+ 9 \cdot 4 = 300 \end{aligned}\text{。}$ 对 $n = 110$ ，此时 $91 \cdot 110 = 10010 \ge 10^4$ ，所以有十项等于 $4$ ，且 $f(110) = 18 + 81 \cdot 3$ $+ 10 \cdot 4 = 301 \gt 300$ 。

由单调性可知，最大的有效 $n$ 是 $109$ 。

Each term $\lfloor \log_{10}(kn) \rfloor$ is nondecreasing in $n,$ so $f$ is nondecreasing and we just locate where it passes $300.$ For $n = 100:$ the products $kn$ run from $100$ to $10^4,$ giving $\lfloor \log_{10} \rfloor = 2$ for $k \le 9,$ $3$ for $10 \le k \le 99,$ and $4$ for $k = 100,$ so $f(100) = 9 \cdot 2 + 90 \cdot 3$ $+ 4 = 292.$

For $n = 109:$ since $9 \cdot 109 = 981 \lt 1000$ and $91 \cdot 109 = 9919 \lt 10^4,$ the terms are $2$ for $k \le 9,$ $3$ for $10 \le k \le 91,$ and $4$ for $92 \le k \le 100:$ $\begin{aligned} f(109) &= 9 \cdot 2 + 82 \cdot 3 \\ &\quad {}+ 9 \cdot 4 = 300. \end{aligned}$ For $n = 110:$ now $91 \cdot 110 = 10010 \ge 10^4,$ so ten terms equal $4$ and $f(110) = 18 + 81 \cdot 3$ $+ 10 \cdot 4 = 301 \gt 300.$

By monotonicity, the largest valid $n$ is $109.$

2010 AIME I 第 14 题

答案：109

难度评级：3060

小提示：

大提示：

解答：

其他年份的第 14 题