AMC 10 · 2011 · #24

학년 8 arithmetic

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

slope-interceptcoordinate-geometryfraction-arithmetic optimization ↑ 선수 지식: slope-intercept

📏 긴 풀이 💡 4 개 인사이트

문제

$xy$ -좌표계에서 격자점이란 $x$ 와 $y$ 가 모두 정수인 점 $(x, y)$ 를 말한다. $\frac{1}{2} < m < a$ 인 모든 $m$ 에 대해, $y = mx +2$ 의 그래프는 $0 < x \le 100$ 인 어떤 격자점도 지나지 않는다. $a$ 가 가질 수 있는 최댓값은 얼마인가?

답을 골라 클릭하세요.

(A)

$\frac{51}{101}$

(B)

$\frac{50}{99}$

(C)

$\frac{51}{100}$

(D)

$\frac{52}{101}$

(E)

$\frac{13}{25}$

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 직선 $y = mx + 2$ 가 $1 \le x \le 100$ 인 모든 격자점을 지나지 않아야 하고, 이 조건이 열린구간 $\left(\tfrac{1}{2}, a\right)$ 안의 모든 기울기 $m$ 에 대해 성립해야 한다. 이때 가능한 $a$ 의 최댓값을 구하라.

주어진 것: 격자점이란 두 좌표가 모두 정수인 점 $(x,y)$ 이다; 직선은 $y = mx + 2$ 이다; 기울기 $m$ 은 열린구간 $\left(\tfrac{1}{2}, a\right)$ 안을 움직인다; "격자점을 지나지 않는다"는 $1 \le x \le 100$ 인 모든 정수 $x$ 에 대해 성립해야 한다; 선택지: (A) $\tfrac{51}{101}$, (B) $\tfrac{50}{99}$, (C) $\tfrac{51}{100}$, (D) $\tfrac{52}{101}$, (E) $\tfrac{13}{25}$

구하는 것: $a$ 의 최댓값

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #16 관점 바꾸기, #4 변수 도입하기, #3 가능성 지우기

문제 전체가 경계값 찾기이므로 도구 #14(극단의 원리)가 주도구이다. 가장 큰 안전한 $a$ 는 $\tfrac{1}{2}$ 바로 위에 있는 단 하나의 "금지된" 기울기가 정한다. 그 금지된 기울기를 보려면 도구 #16(관점 바꾸기)로 "직선이 격자점을 지난다"를 "기울기가 분모 $x \le 100$ 인 분수 $k/x$ 와 같다"로 바꾼다. 도구 #4(변수 도입하기)로 그 분수에 이름을 붙여 $\tfrac{1}{2}$ 위로 얼마나 떨어져 있는지 잰다. 마지막으로 도구 #3(가능성 지우기)로 다섯 선택지를 경계값과 대조하여 짝수 분모의 함정 $\tfrac{51}{100}$ 을 걸러낸다.

실행 — 정답: B

#16 관점 바꾸기 8.F.A.3 단계 1

기울기가 분수인지의 문제로 바꾸기

$y = mx + 2$ 에서 정수 $x$ 일 때 높이는 $y = mx + 2$ 이다.
$2$ 는 이미 정수이므로 $y$ 가 정수가 되는 것은 $mx$ 가 정수일 때뿐이다.
따라서 직선이 $1 \le x \le 100$ 인 격자점을 지나는 것은 곧 어떤 정수 $k$ 에 대해 $mx = k$, 즉 기울기가 분모 $x \le 100$ 인 분수 $m = \tfrac{k}{x}$ 와 같을 때이다.
격자점을 피한다는 것은 이런 분수를 모두 피한다는 뜻이다.

$$y = mx + 2 \in \mathbb{Z} \iff mx \in \mathbb{Z} \iff m = \tfrac{k}{x}$$

💡 정수 $2$ 를 더해도 높이가 정수인지 아닌지는 바뀌지 않으므로 $mx$ 부분만 따지면 된다.

#4 변수 도입하기 6.EE.B.6 단계 2

a 의 목표값에 이름 붙이기

열린구간 $\left(\tfrac{1}{2}, a\right)$ 이 금지된 분수 $\tfrac{k}{x}$ ($x \le 100$) 를 하나도 포함하지 않아야 한다.
$\tfrac{1}{2}$ 보다 큰 그런 분수 중 가장 작은 것을 $f$ 라 하자.
그러면 $a \le f$ 인 동안 구간은 깨끗하게 유지되고, $a$ 를 $f$ 너머로 밀면 $f$ 를 삼켜 격자점을 지나게 된다.
따라서 $a$ 의 최댓값은 $\tfrac{1}{2}$ 위의 첫 금지 분수와 같다.

$$a_{\max} = \min\left\{ \tfrac{k}{x} > \tfrac{1}{2} : 1 \le x \le 100 \right\}$$

💡 가장 넓은 안전 구간은 가장 가까운 장애물 바로 앞에서 멈추므로, $\tfrac{1}{2}$ 위의 가장 가까운 장애물을 찾으면 된다.

#14 극단의 원리 5.NF.A.1 단계 3

분모가 고정될 때 절반 위의 간격

분모 $x$ 를 고정하자.
$\tfrac{k}{x} > \tfrac{1}{2}$ 를 만드는 가장 작은 분자는 $k > \tfrac{x}{2}$ 를 만족하는 가장 작은 정수 $k$ 이다.
그 분수가 $\tfrac{1}{2}$ 위로 떨어진 거리는 $\tfrac{k}{x} - \tfrac{1}{2} = \tfrac{2k - x}{2x}$ 이다.
$\tfrac{k}{x} > \tfrac{1}{2}$ 이므로 분자 $2k - x$ 는 양의 정수이고, 따라서 이 간격은 최소 $\tfrac{1}{2x}$ 이다.

$$\tfrac{k}{x} - \tfrac{1}{2} = \tfrac{2k - x}{2x} \ge \tfrac{1}{2x}$$

💡 공통분모 $2x$ 로 다시 쓰면 "절반에 얼마나 가까운가"가 단순한 정수 분자 $2k-x$ 로 바뀐다.

#14 극단의 원리 2.OA.C.3 단계 4

홀수 분모가 가장 가깝다

간격 $\tfrac{2k - x}{2x}$ 를 작게 하려면 분자 $2k - x$ 가 $1$ 이면 된다.
그런데 $2k - x = 1$ 이면 $x = 2k - 1$ 로 홀수이다.
만약 $x$ 가 짝수이면 $2k - x$ 도 짝수라 최소 $2$ 가 되어, 최소 간격이 $\tfrac{2}{2x} = \tfrac{1}{x}$ 로 두 배가 된다.
즉 홀수 분모는 짝수 분모보다 $\tfrac{1}{2}$ 에 두 배 더 바짝 붙을 수 있다.

$$x \text{ 홀수} \Rightarrow \text{간격} = \tfrac{1}{2x}; \quad x \text{ 짝수} \Rightarrow \text{간격} \ge \tfrac{1}{x}$$

💡 분자가 정확히 $1$ 이 되려면 분모가 홀수여야 하고, 짝수 분모는 어쩔 수 없이 $2$ 로 건너뛴다.

#14 극단의 원리 4.NF.A.2 단계 5

분모를 최대까지 밀기

$x$ 가 홀수이면 간격 $\tfrac{1}{2x}$ 은 $x$ 가 커질수록 작아지므로, 허용되는 가장 큰 홀수 분모 $x = 99$ 를 택한다.
$k > \tfrac{99}{2}$ 인 가장 작은 $k$ 는 $k = 50$ 이고, 분수 $\tfrac{50}{99}$ 의 간격은 $\tfrac{1}{198}$ 이다.
가장 좋은 짝수 경쟁자는 $x = 100$ 으로 $\tfrac{51}{100}$, 간격 $\tfrac{1}{100} = \tfrac{1.98}{198}$ 이라 더 크다.
$\tfrac{1}{198}$ 이 다른 모든 분모의 간격을 이기므로 $\tfrac{50}{99}$ 가 $\tfrac{1}{2}$ 위의 가장 가까운 금지 분수이다.

$$\tfrac{50}{99} - \tfrac{1}{2} = \tfrac{1}{198} < \tfrac{1}{100} = \tfrac{51}{100} - \tfrac{1}{2}$$

💡 단위분수 간격은 분모가 클수록 작아지므로 홀수 분모를 $99$ 까지 끝까지 올린다.

#3 가능성 지우기 7.NS.A.1 단계 6

경계값과 답 확인하기

구간 $\left(\tfrac{1}{2}, \tfrac{50}{99}\right)$ 은 분모 $\le 100$ 인 분수를 하나도 포함하지 않으므로 그 안의 모든 기울기는 격자점을 피한다.
구간이 열려 있어 $\tfrac{50}{99}$ 자체는 제외되므로 $a = \tfrac{50}{99}$ 는 안전하다.
더 큰 $a$ 는 $m = \tfrac{50}{99}$ 를 들여보내고, 이 직선은 $(99, 52)$ 를 지난다.
선택지를 확인하면 $\tfrac{51}{100}$, $\tfrac{52}{101}$, $\tfrac{13}{25}$ 는 모두 $\tfrac{50}{99}$ 보다 커서 격자점을 들여보낸다.
$\tfrac{51}{101} \approx 0.50495$ 는 안전하지만 $\tfrac{50}{99} \approx 0.50505$ 보다 작아 최댓값이 아니다.
유효한 최댓값은 $\tfrac{50}{99}$, 즉 (B)이다.

$$a_{\max} = \tfrac{50}{99} \Rightarrow \textbf{(B)}$$

💡 가장 좋은 $a$ 는 가장 가까운 금지 분수 바로 그 자리에 있고, 열린구간 덕분에 그 끝값을 상한으로 삼을 수 있다.

[1] #16 8.F.A.3 $y = mx + 2$ 에서 정수 $x$ 일 때 높이는 $y = mx + 2$ 이다. $2$ 는 이미 정수이므로 $y$ 가 정수가 되는 것은 $

[2] #4 6.EE.B.6 열린구간 $\left(\tfrac{1}{2}, a\right)$ 이 금지된 분수 $\tfrac{k}{x}$ ($x \le 100$) 를 하나도

[3] #14 5.NF.A.1 분모 $x$ 를 고정하자. $\tfrac{k}{x} > \tfrac{1}{2}$ 를 만드는 가장 작은 분자는 $k > \tfrac{x}{2}$

[4] #14 2.OA.C.3 간격 $\tfrac{2k - x}{2x}$ 를 작게 하려면 분자 $2k - x$ 가 $1$ 이면 된다. 그런데 $2k - x = 1$ 이면 $x

[5] #14 4.NF.A.2 $x$ 가 홀수이면 간격 $\tfrac{1}{2x}$ 은 $x$ 가 커질수록 작아지므로, 허용되는 가장 큰 홀수 분모 $x = 99$ 를 택한다

[6] #3 7.NS.A.1 구간 $\left(\tfrac{1}{2}, \tfrac{50}{99}\right)$ 은 분모 $\le 100$ 인 분수를 하나도 포함하지 않으므

검토

합리성 확인: 다섯 선택지가 모두 $\tfrac{1}{2}$ 바로 위에 몰려 있는데, 이는 답이 $0.5$ 보다 아주 조금 큰 분수여야 한다는 점과 맞는다. 수치로 $\tfrac{50}{99} \approx 0.50505$ 이고, 이보다 작은 선택지는 $\tfrac{51}{101} \approx 0.50495$ 뿐인데 이는 안전하지만 최대가 아닌 아슬아슬한 함정이다. 매력적인 오답 $\tfrac{51}{100} = 0.51$ 은 가장 좋은 짝수 분모 분수이며, 우리의 홀짝 판단 단계가 바로 이것을 걸러낸다. 홀수 분모 $99$ 가 $\tfrac{1}{2}$ 에 두 배 더 바짝 붙기 때문이다. 이긴 기울기 $\tfrac{50}{99}$ 는 실제로 격자점 $(99, 99\cdot\tfrac{50}{99}+2) = (99, 52)$ 를 지나므로 그것이 진짜 첫 장애물임이 확인된다.

대안 접근: 메디언트(Farey 수열) 관점: 분모 $\le 100$ 인 분수 중 $\tfrac{1}{2}$ 의 오른쪽 이웃은 $x$ 를 최대로 하며 $2k - x = 1$ 을 푸는 것, 즉 Farey 수열 $F_{100}$ 에서 $\tfrac{1}{2}$ 위쪽으로 가장 가까운 분수 $\tfrac{k}{x}$ 를 찾는 것이다. 그 이웃은 $\tfrac{50}{99}$ 인데, $\left|\tfrac{50}{99} - \tfrac{1}{2}\right| = \tfrac{1}{2 \cdot 99}$ 이 가능한 최소 교차차이이기 때문이다. 이는 분모를 하나하나 확인하지 않고도 (B)를 다시 얻는다.

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

8.F.A.3 Interpret the equation y = mx + b as defining a linear function ($y = mx + 2$ 를 기울기 $m$ 인 직선으로 읽고, 격자점을 지나는 것이 기울기가 분수 $k/x$ 와 같을 때뿐임을 파악하는 데 사용.)
6.EE.B.6 Use variables to represent numbers and write expressions to solve problems (금지된 기울기 $k/x$ 에 이름을 붙이고 목표 $a$ 를 $1/2$ 위의 가장 작은 분수로 정의하는 데 사용.)
5.NF.A.1 Add and subtract fractions with unlike denominators (간격 $\tfrac{k}{x} - \tfrac{1}{2} = \tfrac{2k-x}{2x}$ 를 공통분모 $2x$ 위에서 계산하는 데 사용.)
2.OA.C.3 Determine whether a group of objects has an odd or even number ($2k-x=1$ 이 $x$ 를 홀수로 강제하므로 짝수 분모는 간격 $1/x$ 까지밖에 못 간다는 홀짝 논증에 사용.)
4.NF.A.2 Compare two fractions with different numerators and different denominators (후보 간격 $\tfrac{1}{198}$ ($\tfrac{50}{99}$ 에서) 과 $\tfrac{1}{100}$ ($\tfrac{51}{100}$ 에서) 을 비교해 가장 가까운 분수를 고르는 데 사용.)
7.NS.A.1 Apply and extend understanding of addition and subtraction to rational numbers (선택지들을 $\tfrac{50}{99}$ 를 중심으로 정렬해 그것이 유효한 $a$ 의 최댓값임을 확인하는 데 사용.)

⭐ "직선이 모든 격자점을 피한다"를 "기울기가 $x \le 100$ 인 어떤 분수 $k/x$ 도 아니다"로 바꾼 뒤, $\tfrac{1}{2}$ 위쪽으로 가장 바짝 붙는 분수를 찾으면 된다. 홀수 분모가 이기고, $x=99$ 가 $\tfrac{50}{99}$ 를 준다.