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 개 인사이트

문제

S 를 {(x, y) : 1 ≤ x ≤ 30, 1 ≤ y ≤ 30, x, y ∈ Z} 인 30 × 30 격자점 집합이라 하자 (|S| = 900). 직선 y = m x 의 "위쪽 또는 위에" 즉 y ≤ m x 를 만족하는 S 의 점이 정확히 300 개가 되도록 하는 기울기 m 은 길이

\frac{a}{b}

(기약분수) 인 구간을 이룬다. 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.

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

열 x 마다 y ≤ mx 인 점이 min(⌊mx⌋, 30) 개 → N(m) = Σ min(⌊mx⌋, 30) (m ≤ 1 이면 상한 30 무관).

N(m) = Σ_x = 1³⁰ min(⌊ m x ⌋, 30)

2STEP 2

넓이 근사: 삼각형이 정사각형(900)의 $\frac{1}{3}$ , $\frac{450m}{900}$ = $\frac{1}{3}$ → m ≈ $\frac{2}{3}$ , 30·( $\frac{2}{3}$ ) = 20 ≤ 30 안전.

m ≈

\frac{2}{3}

3STEP 3

x 를 3 으로 나눈 나머지로 묶으면 세 항 합이 6k − 3, k = 1..10 합이 N( $\frac{2}{3}$ ) = 300. ✓

\frac{2}{3}

) = Σ_k = 1¹⁰(6k - 3) = 300

4STEP 4

$\frac{2}{3}$ 바로 아래면 직선 위 10 점이 빠져 N 이 300 → 290, 따라서 m_lo = $\frac{2}{3}$ 이 하한(포함).

m_lo =

\frac{2}{3}

(포함)

5STEP 5

다음 점프는 $\frac{2}{3}$ 위 가장 작은 $\frac{k}{x}$ — $\frac{3k − 2x}{3x}$ 최소화는 분자 3k − 2x = 1, x 최대화가 관건.

min

\frac{k}{x}

\frac{2}{3}

\frac{1}{3x}

; 최대 x with 3k - 2x = 1

6STEP 6

3k − 2x = 1 의 x ≤ 30 최대해는 x = 28 (t = 9), 그래서 m_hi = $\frac{19}{28}$ , 구간 [ $\frac{2}{3}$ , $\frac{19}{28}$ ).

m_hi =

\frac{19}{28}

, m ∈ [

\frac{2}{3}

\frac{19}{28}

)

7STEP 7

구간 길이: $\frac{19}{28}$ − $\frac{2}{3}$ = $\frac{57 − 56}{84}$ = $\frac{1}{84}$ (기약), 그래서 a + b = 1 + 84 = 85, 답 (E).

\frac{1}{84}

, a + b = 1 + 84 = 85 → (E)

정답

~85

감각 점검.

\frac{2}{3}

≈ 0.6667,

\frac{19}{28}

≈ 0.6786, 구간 길이 ≈ 0.012. 30 × 30 격자에서 한 격자점이 들거나 빠지는 Δ m 평균 간격은 대략 이 정도라 합리적. 또한 m =

\frac{19}{28}

에서 격자점 (28, 19) 가 "위 또는 위에" 에 새로 합류해 N 이 300 → 301 — 구간이 왼쪽 닫힘 (직선 위 격자점 포함) 오른쪽 열림 (다음 점이 합류하기 직전) 인 게 일관.

💡핵심 정리

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

비슷한 유형 더 풀어보기