← Sensim Lab Sensim Math

AMC 10 · 2021 · #25

학년 8 number-theory
유형 Lattice / Grid Pattern from Small Cases
floor-functionlinear-diophantinecoordinate-geometryfraction-arithmetic easier-related-problempattern-recognitionbound-inequality-then-enumerate ↑ 선수 지식: floor-functioncoordinate-geometry
📏 긴 풀이 💡 4 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)
~31
(B)
~47
(C)
~62
(D)
~72
(E)
~85
보기 방식:

도구 + 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$

이해

문제 재정리: $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$

계획

주요 도구: #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$.

⭐ 가장 어려운 이 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$.

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.