AMC 10 · 2005 · #12

학년 8 number-theory
유형 Lattice / Grid Pattern from Small Cases └ 세부 유형 Grid Diagonal Cell Count
coordinate-geometrygcddivisibility-rules convert-to-algebrasystematic-enumeration ↑ 선수 지식: slope-interceptgcdfraction-arithmetic
📏 중간 풀이 💡 2 개 인사이트
문제
어떤 직선이 점 1, 1 과 점 100, 1000 을 잇는다. 그 사이 선분 위에서 두 좌표가 모두 정수인 점의 개수를 구하여라.

답을 골라 클릭하세요.

(A)
0
(B)
2
(C)
3
(D)
8
(E)
9
풀이 과정
전략 변수 도입하기

그림 전체를 옮겨 A를 원점에 놓아도 잃는 것이 없다. 정수만큼 평행이동하므로 정수 좌표를 가진 점은 그대로 정수 좌표를 유지하고, 직선의 식은 가장 단순해진다. 그다음 움직이는 x좌표를 변수로 두면 "이 점이 격자점인가?"라는 기하 질문이 정수 하나에 대한 배수 판정 문제로 바뀐다. 그림을 훑어보는 대신 정확히 답할 수 있게 된다.

1STEP 1

A를 원점으로 옮기기

정수 평행이동으로 개수를 바꾸지 않고 한 끝점을 원점으로 옮긴다.

(x,y)↦(x-1, y-1), A(1,1)↦(0,0), B(100,1000)↦(99,999)
2STEP 2

기울기를 기약분수로

기울기가 약분되고 약분된 꼴만이 의미가 있다.

m=(1000-1)/(100-1)=999/99=111/11, gcd(111,11)=1
3STEP 3

격자점 조건을 배수 조건으로

격자점이라는 것이 하나의 배수 조건이 된다.

y=111x/11inZ⇔ 11 ∣ 111x⇔ 11 ∣ x
4STEP 4

11의 배수 나열하기

범위 안의 배수를 나열하면 8개다.

x∈{11,22,33,44,55,66,77,88} → 8개, 원래 좌표계에서는 (12,112),…,(89,889)
5STEP 5

최대공약수 규칙으로 확인

최대공약수 규칙도 8을 확인해 준다, 보기 (D).

gcd(99,999)=9, 9-1=8
정답
8
내부 격자점 8개는 선분 AB를 9등분하고, 각 조각은 (11,111)만큼의 걸음이다. A(1,1)에 이 걸음을 9번 더하면 (1+99, 1+999)=(100,1000)=B가 되어 계산이 정확히 닫힌다. 또한 개수는 가능한 x값의 수인 99보다 작아야 하는데 8은 충분히 작다. 보기 (E) 9가 전형적인 함정이다. 9는 조각의 개수이거나 B를 잘못 포함해서 센 값이다.
💡핵심 정리

기울기를 기약분수로 만들면 직선은 줄어든 가로 걸음의 정수 배마다만 격자점을 밟으니, 그 걸음이 양 끝 사이에 몇 번 들어가는지 세면 된다.

  • A를 원점으로 옮기기
  • 기울기를 기약분수로
  • 격자점 조건을 배수 조건으로
  • 11의 배수 나열하기
  • 최대공약수 규칙으로 확인

비슷한 유형 더 풀어보기

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