AMC 10 · 2021 · #25

학년 8 number-theory

유형 Lattice / Grid Pattern from Small Cases └ 세부 유형 Lattice Constraint Analysis

floor-functionlinear-diophantinecoordinate-geometryfraction-arithmetic easier-related-problempattern-recognitionbound-inequality-then-enumerate ↑ 선수 지식: floor-functioncoordinate-geometry

📏 긴 풀이 💡 4 개 인사이트

문제

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?$

답을 골라 클릭하세요.

(A)

~31

(B)

~47

(C)

~62

(D)

~72

(E)

~85

AMC 10 2021 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $S$ 를 $\{(x, y) : 1 \le x \le 30,\; 1 \le y \le 30,\; x, y \in \mathbb{Z}\}$ 인 $30 \times 30$ 격자점 집합이라 하자 ($|S| = 900$). 직선 $y = m x$ 의 "위쪽 또는 위에" 즉 $y \le m x$ 를 만족하는 $S$ 의 점이 정확히 $300$ 개가 되도록 하는 기울기 $m$ 은 길이 $\tfrac{a}{b}$ (기약분수) 인 구간을 이룬다. $a + b$ 를 구하시오.

주어진 것: $S = \{(x, y) : 1 \le x, y \le 30,\; x, y \in \mathbb{Z}\}$, $|S| = 900$; 직선 $y = m x$ 는 원점을 지남; $y \le m x$ 를 만족하는 $S$ 의 점이 정확히 $300$ 개; 가능한 $m$ 은 길이 $\tfrac{a}{b}$ (기약분수) 인 구간; 선택지: (A) $31$, (B) $47$, (C) $62$, (D) $72$, (E) $85$

구하는 것: $a + b$

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #1 그림 그리기, #7 작은 문제로 쪼개기, #3 가능성 지우기

도구 #9 (더 쉬운 문제) — 연속 넓이 근사 (삼각형 넓이가 정사각형의 $\tfrac{1}{3}$) 로 $m \approx \tfrac{2}{3}$ 추측한 뒤 정확 검증. 도구 #5 (패턴) — $\sum_{x = 1}^{30} \lfloor \tfrac{2x}{3} \rfloor$ 의 $30$ 항을 $x \bmod 3$ 으로 묶어 등차 합 공식. 도구 #1 (그림) — $30 \times 30$ 격자에 $y = \tfrac{2}{3} x$ 가 $(3, 2), (6, 4), \ldots, (30, 20)$ 을 정확히 지나가는 모습. 도구 #7 (쪼개기) — 구간 하한과 상한을 별도로. 도구 #3 (가능성 지우기) — $a + b$ 가 선택지 중 하나여야.

실행 — 정답: E

#7 작은 문제로 쪼개기 8.F.A.1 단계 1

"직선 위 또는 아래의 격자점 수" 를 합으로 표현.
각 $x \in \{1, \ldots, 30\}$ 에 대해 그 열 $\{(x, 1), \ldots, (x, 30)\}$ 에서 $y \le m x$ 인 점 수 $= \min(\lfloor m x \rfloor, 30)$.
따라서 $N(m) = \sum_{x = 1}^{30} \min(\lfloor m x \rfloor, 30)$.
$m \le 1$ 이면 $\lfloor m x \rfloor \le 30$ 이라 $\min$ 항상 비활성 — $N(m) = \sum_{x = 1}^{30} \lfloor m x \rfloor$.

$$N(m) = \sum_{x = 1}^{30} \min(\lfloor m x \rfloor, 30)$$

💡 열마다 "$m x$ 이하의 격자 $y$ 개수" 를 세면 그게 바로 $\lfloor m x \rfloor$ (천장 $30$ 제한).

#9 더 쉬운 문제로 줄이기 7.G.B.6 단계 2

넓이 근사로 $m$ 추측 (도구 #9).
직선 $y = m x$ 가 $30 \times 30$ 연속 정사각형 (넓이 $900$) 에서 떼어내는 삼각형 넓이 $= \tfrac{1}{2} \cdot 30 \cdot 30 m = 450 m$ ($m \le 1$ 가정).
$300$ 격자점 $\approx \tfrac{1}{3} \cdot 900$, 그래서 $\tfrac{450 m}{900} = \tfrac{1}{3} \Rightarrow m \approx \tfrac{2}{3}$.
$m = \tfrac{2}{3}$ 면 $30 m = 20 \le 30$ 이라 $\min$ 안전.

$$m \approx \tfrac{2}{3}$$

💡 연속 넓이로 첫 후보 — 그다음 격자점 개수를 정확히 검증.

#5 패턴 찾기 8.F.B.4 단계 3

$N(\tfrac{2}{3}) = 300$ 검증.
$x = 1, \ldots, 30$ 을 셋씩 묶음 (도구 #5).
$x = 3k - 2$: $\lfloor \tfrac{2}{3}(3k - 2) \rfloor = \lfloor 2k - \tfrac{4}{3} \rfloor = 2k - 2$.
$x = 3k - 1$: $\lfloor 2k - \tfrac{2}{3} \rfloor = 2k - 1$.
$x = 3k$: $2k$.
세 항 합 $= 6k - 3$.
전체 $= \sum_{k = 1}^{10}(6k - 3) = 6 \cdot \tfrac{10 \cdot 11}{2} - 30 = 330 - 30 = 300$.
✓

$$N(\tfrac{2}{3}) = \sum_{k = 1}^{10}(6k - 3) = 300$$

💡 $x \bmod 3$ 으로 묶으면 각 잔여류가 등차로 깔끔하게 떨어짐.

#1 그림 그리기 8.F.A.1 단계 4

구간 하한 $m_{\text{lo}}$.
$m = \tfrac{2}{3} - \varepsilon$ 이면 $x = 3k$ 에서 $m x = 2k - 3k\varepsilon < 2k$, 그래서 $\lfloor m x \rfloor$ 가 $2k$ 에서 $2k - 1$ 로 떨어짐 — $10$ 개 값 모두.
$N$ 이 $300$ 에서 $290$ 으로 감소.
따라서 $m = \tfrac{2}{3}$ 가 $N = 300$ 인 최소 기울기 (포함).
직선 $y = \tfrac{2}{3} x$ 가 정확히 격자점 $(3, 2), (6, 4), \ldots, (30, 20)$ 을 지남 — 이들이 "위 또는 위에" 의 카운트에 포함.

$$m_{\text{lo}} = \tfrac{2}{3} \;\text{(포함)}$$

💡 직선이 살짝 떨어지면 격자점 $(3, 2), (6, 4), \ldots$ 가 정확히 $10$ 개 빠짐.

#7 작은 문제로 쪼개기 7.NS.A.3 단계 5

구간 상한 $m_{\text{hi}}$.
$N(m)$ 은 $m = \tfrac{k}{x}$ ($1 \le x \le 30$, $k$ 양의 정수) 형태 값을 지날 때만 점프.
$\tfrac{2}{3}$ 보다 큰 가장 작은 $\tfrac{k}{x}$ 를 찾음.
$\tfrac{k}{x} - \tfrac{2}{3} = \tfrac{3k - 2x}{3x}$ 최소화.
분자 $3k - 2x > 0$ 정수 $\Rightarrow$ 최소 $1$, 그때 차이 $= \tfrac{1}{3x}$ — $x$ 를 최대화하면 됨.

$$\min \tfrac{k}{x} - \tfrac{2}{3} = \tfrac{1}{3x};\;\text{최대 } x \text{ with } 3k - 2x = 1$$

💡 $\tfrac{2}{3}$ 바로 위 가장 작은 분수는 "분모 가능한 한 크게" 가 정답.

#7 작은 문제로 쪼개기 7.NS.A.3 단계 6

디오판토스 $3k - 2x = 1$, $1 \le x \le 30$ 풀이.
일반해 $(k, x) = (1 + 2t, 1 + 3t)$, 정수 $t \ge 0$.
$x \le 30 \Rightarrow 1 + 3t \le 30 \Rightarrow t \le 9$.
최대 $t = 9$ 면 $x = 28$, $k = 19$.
검증: $3 \cdot 19 - 2 \cdot 28 = 57 - 56 = 1$ ✓.
$m_{\text{hi}} = \tfrac{19}{28}$ (비포함; $m = \tfrac{19}{28}$ 일 때 $\lfloor m \cdot 28 \rfloor$ 가 $18$ 에서 $19$ 로 올라 $N$ 이 $301$).
구간 $[\tfrac{2}{3}, \tfrac{19}{28})$.

$$m_{\text{hi}} = \tfrac{19}{28},\;\; m \in [\tfrac{2}{3}, \tfrac{19}{28})$$

💡 $t = 9$ 가 $x$ 를 $28$ 까지 끌어올림 — $30$ 이하 최대 가능값.

#3 가능성 지우기 5.NF.A.1 단계 7

구간 길이: $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{19 \cdot 3 - 2 \cdot 28}{84} = \tfrac{57 - 56}{84} = \tfrac{1}{84}$.
$\gcd(1, 84) = 1$ 이라 기약.
$a = 1, b = 84$, $a + b = 85$.
선택지 (E).

$$\tfrac{1}{84},\;\; a + b = 1 + 84 = 85 \Rightarrow \textbf{(E)}$$

💡 공통분모 빼기로 깔끔한 $\tfrac{1}{84}$ — $85$ 가 선택지 (E).

[1] #7 8.F.A.1 "직선 위 또는 아래의 격자점 수" 를 합으로 표현. 각 $x \in \{1, \ldots, 30\}$ 에 대해 그 열 ${(x, 1), \l

[2] #9 7.G.B.6 넓이 근사로 $m$ 추측 (도구 #9). 직선 $y = m x$ 가 $30 \times 30$ 연속 정사각형 (넓이 $900$) 에서 떼어내는

[3] #5 8.F.B.4 $N(\tfrac{2}{3}) = 300$ 검증. $x = 1, \ldots, 30$ 을 셋씩 묶음 (도구 #5). $x = 3k - 2$: $

[4] #1 8.F.A.1 구간 하한 $m_{\text{lo}}$. $m = \tfrac{2}{3} - \varepsilon$ 이면 $x = 3k$ 에서 $m x = 2k

[5] #7 7.NS.A.3 구간 상한 $m_{\text{hi}}$. $N(m)$ 은 $m = \tfrac{k}{x}$ ($1 \le x \le 30$, $k$ 양의 정수)

[6] #7 7.NS.A.3 디오판토스 $3k - 2x = 1$, $1 \le x \le 30$ 풀이. 일반해 $(k, x) = (1 + 2t, 1 + 3t)$, 정수 $t

[7] #3 5.NF.A.1 구간 길이: $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{19 \cdot 3 - 2 \cdot 28}{84} = \t

검토

합리성 확인: 감각 점검. $\tfrac{2}{3} \approx 0.6667$, $\tfrac{19}{28} \approx 0.6786$, 구간 길이 $\approx 0.012$. $30 \times 30$ 격자에서 한 격자점이 들거나 빠지는 $\Delta m$ 평균 간격은 대략 이 정도라 합리적. 또한 $m = \tfrac{19}{28}$ 에서 격자점 $(28, 19)$ 가 "위 또는 위에" 에 새로 합류해 $N$ 이 $300 \to 301$ — 구간이 왼쪽 닫힘 (직선 위 격자점 포함) 오른쪽 열림 (다음 점이 합류하기 직전) 인 게 일관.

대안 접근: 도구 #5 (패턴) — 디오판토스 없이도 각 $x = 1, \ldots, 30$ 에 대해 $\tfrac{2}{3}$ 보다 큰 가장 작은 $\tfrac{k}{x}$ 를 직접 만들고 최소를 찾기. 후보 $\tfrac{17}{25} = \tfrac{2}{3} + \tfrac{1}{75}$, $\tfrac{13}{19} = \tfrac{2}{3} + \tfrac{1}{57}$ 등 모두 $\tfrac{1}{84} = \tfrac{19}{28} - \tfrac{2}{3}$ 보다 큼 — $x = 28$ 이 최적임을 직접 확인.

사용된 CCSS 표준 (최저 학년 8)

5.NF.A.1 분모가 다른 분수의 덧셈과 뺄셈 ($\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84}$ 를 공통분모 $84$ 로 계산.)
7.G.B.6 넓이·겉넓이·부피 관련 실생활 문제 해결 (삼각형/정사각형 넓이 비 $= \tfrac{1}{3}$ 로 $m \approx \tfrac{2}{3}$ 초기 추정.)
7.NS.A.3 유리수 사칙연산을 이용한 실생활 문제 해결 (디오판토스 $3k - 2x = 1$ ($1 \le x \le 30$) 풀이 후 $\tfrac{1}{3x}$ 최소화.)
8.F.A.1 함수의 정의 (입력당 출력 하나) ($N(m) = \sum_{x = 1}^{30} \lfloor m x \rfloor$ 를 $m$ 의 계단 함수로 다루고 $\tfrac{k}{x}$ 마다 점프 분석.)
8.F.B.4 두 양 사이 선형 관계 모델링 함수 구성 ($x \bmod 3$ 잔여류로 묶어 $N(\tfrac{2}{3}) = \sum_{k = 1}^{10}(6k - 3)$ 등차 합 표현.)

⭐ 가장 어려운 이 AMC 10 문제도 7-8학년 수준 추정과 정수론으로 풀려요 — 정사각형 넓이의 $\tfrac{1}{3}$ 에서 $m \approx \tfrac{2}{3}$ 를 추측한 뒤 셋씩 묶어 정확히 $300$ 점임을 확인; 다음 점프는 $\tfrac{2}{3}$ 바로 위 가장 작은 $\tfrac{k}{x}$ ($x \le 30$) 이고 $3k - 2x = 1$ 의 최대 $x = 28$ 에서 $\tfrac{19}{28}$; 구간 길이 $\tfrac{19}{28} - \tfrac{2}{3} = \tfrac{1}{84}$, 답 $a + b = 1 + 84 = 85$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: E

검토

사용된 CCSS 표준 (최저 학년 8)

비슷한 유형 더 풀어보기