AMC12 2021 B

AMC12 2021 B · Q25

AMC12 2021 B · Q25. It mainly tests Inequalities with floors/ceilings (basic), Casework.

Let $S$ be the set of lattice points in the coordinate plane, both of whose coordinates are integers between $1$ and $30,$ inclusive. Exactly $300$ points in $S$ lie on or below a line with equation $y=mx.$ The possible values of $m$ lie in an interval of length $\frac ab,$ where $a$ and $b$ are relatively prime positive integers. What is $a+b?$

设 $S$ 是坐标平面中坐标均为 $1$ 到 $30$（包含）整数的格点。恰有 $300$ 个点位于直线 $y=mx$ 上或下方。$m$ 的可能值位于长度为 $\frac ab$ 的区间中，其中 $a$ 和 $b$ 互质正整数。求 $a+b$？

(A) 31 31

(B) 47 47

(D) 72 72

(E) 85 85

Answer

Correct choice: (E)

正确答案：（E）

Solution

First, we find a numerical representation for the number of lattice points in $S$ that are under the line $y=mx.$ For any value of $x,$ the highest lattice point under $y=mx$ is $\lfloor mx \rfloor.$ Because every lattice point from $(x, 1)$ to $(x, \lfloor mx \rfloor)$ is under the line, the total number of lattice points under the line is $\sum_{x=1}^{30}(\lfloor mx \rfloor).$ Now, we proceed by finding lower and upper bounds for $m.$ To find the lower bound, we start with an approximation. If $300$ lattice points are below the line, then around $\frac{1}{3}$ of the area formed by $S$ is under the line. By using the formula for a triangle's area, we find that when $x=30, y \approx 20.$ Solving for $m$ assuming that $(30, 20)$ is a point on the line, we get $m = \frac{2}{3}.$ Plugging in $m$ to $\sum_{x=1}^{30}(\lfloor mx \rfloor),$ we get: \[\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20\] We have a repeat every $3$ values (every time $y=\frac{2}{3}x$ goes through a lattice point). Thus, we can use arithmetic sequences to calculate the value above: \[\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20\]\[=\frac{20(21)}{2} + 2 + 4 + 6 + \cdots + 18\]\[=210 + \frac{20}{2}\cdot 9\]\[=300\] This means that $\frac{2}{3}$ is a possible value of $m.$ Furthermore, it is the lower bound for $m.$ This is because $y=\frac{2}{3}x$ goes through many points (such as $(21, 14)$). If $m$ was lower, $y=mx$ would no longer go through some of these points, and there would be less than $300$ lattice points under it. Now, we find an upper bound for $m.$ Imagine increasing $m$ slowly and rotating the line $y=mx,$ starting from the lower bound of $m=\frac{2}{3}.$The upper bound for $m$ occurs when $y=mx$ intersects a lattice point again (look at this problem to get a better idea of what's happening: https://artofproblemsolving.com/wiki/index.php/2011_AMC_10B_Problems/Problem_24). In other words, we are looking for the first $m > \frac{2}{3}$ that is expressible as a ratio of positive integers $\frac{p}{q}$ with $q \le 30.$ For each $q=1,\dots,30$, the smallest multiple of $\frac{1}{q}$ which exceeds $\frac{2}{3}$ is $1, \frac{2}{2}, \frac{3}{3}, \frac{3}{4}, \frac{4}{5}, \cdots , \frac{19}{27}, \frac{19}{28}, \frac{20}{29}, \frac{21}{30}$ respectively, and the smallest of these is $\frac{19}{28}.$ Alternatively, see the method of finding upper bounds in solution 2. The lower bound is $\frac{2}{3}$ and the upper bound is $\frac{19}{28}.$ Their difference is $\frac{1}{84},$ so the answer is $1 + 84 = \boxed{85}.$

首先，我们找到 $S$ 中位于直线 $y=mx$ 下方的格点数的数值表示。对于任意 $x$，$y=mx$ 下方的最高格点是 $\lfloor mx \rfloor$。因为从 $(x, 1)$ 到 $(x, \lfloor mx \rfloor)$ 的每个格点都在直线下方，因此直线下方格点的总数是 $\sum_{x=1}^{30}(\lfloor mx \rfloor)$。现在，我们通过寻找 $m$ 的上下界进行。对于下界，我们从近似开始。如果 $300$ 个格点在直线下方，则 $S$ 形成的区域约有 $\frac{1}{3}$ 在直线下方。使用三角形面积公式，当 $x=30$ 时 $y \approx 20$。假设 $(30, 20)$ 在直线上解 $m$ 得 $m = \frac{2}{3}$。代入 $\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor)$，我们得到： \[\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20\] 每 $3$ 个值重复一次（每次 $y=\frac{2}{3}x$ 通过格点时）。因此，可以用等差数列计算上述值： \[\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20\]\[=\frac{20(21)}{2} + 2 + 4 + 6 + \cdots + 18\]\[=210 + \frac{20}{2}\cdot 9\]\[=300\] 这意味着 $\frac{2}{3}$ 是 $m$ 的可能值。而且它是下界。因为 $y=\frac{2}{3}x$ 通过许多点（如 $(21, 14)$）。如果 $m$ 更小，$y=mx$ 将不再通过这些点，下方格点将少于 $300$。现在，寻找 $m$ 的上界。想象缓慢增加 $m$ 并旋转直线 $y=mx$，从下界 $m=\frac{2}{3}$ 开始。上界出现在 $y=mx$ 再次通过格点时（参见此题以更好地理解发生什么：https://artofproblemsolving.com/wiki/index.php/2011_AMC_10B_Problems/Problem_24）。换言之，我们寻找第一个 $m > \frac{2}{3}$，可表示为分母 $q \le 30$ 的正整数比 $\frac{p}{q}$。对于每个 $q=1,\dots,30$，超过 $\frac{2}{3}$ 的 $\frac{1}{q}$ 的最小倍数分别是 $1, \frac{2}{2}, \frac{3}{3}, \frac{3}{4}, \frac{4}{5}, \cdots , \frac{19}{27}, \frac{19}{28}, \frac{20}{29}, \frac{21}{30}$，其中最小的是 $\frac{19}{28}$。或者，见 solution 2 中的寻找上界方法。下界是 $\frac{2}{3}$，上界是 $\frac{19}{28}$。它们的差是 $\frac{1}{84}$，因此答案是 $1 + 84 = \boxed{85}$。

Topics