AMC 10 · 2009 · #22

학년 10 countingnumber-theory

유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search

coordinate-geometryprime-factorizationstars-and-barsshoelace-formula convert-to-algebraidentify-subproblemssystematic-enumeration ↑ 선수 지식: coordinate-geometryprime-factorization

📏 긴 풀이 💡 4 개 인사이트

문제

넓이가 주어진 평행사변형의 한 꼭짓점이 원점이고 다른 둘은 원점을 지나는 직선 위의 격자점이다. 그런 평행사변형의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

720

(C)

784

(D)

2009

(E)

2048

풀이 과정

전략 대수로 바꾸기

그림은 보기보다 훨씬 자유롭지 않다. A 는 원점에 못 박혀 있고, B 는 직선 y = x 위로 끌려가 있으며, D 는 원점을 지나는 정수 기울기 직선 위로 끌려가 있다. 그래서 기울기 k 와 두 x 좌표 s, t 라는 세 개의 자연수만으로 도형 전체가 결정된다. 이 세 문자로 넓이를 쓰면 기하 문제가 (k-1)st = 1,000,000 이라는 식 하나로 무너지고, 남는 것은 도형 문제가 아니라 인수분해 문제다. 함정은 여기서 멈추는 것이다. 이 식은 아직 필요조건일 뿐이어서, 정당한 평행사변형이라면 이런 인수분해가 나온다는 사실만 말해 준다. 인수분해의 개수가 곧 답이 되려면 반대 방향도 확인해야 하므로 두 가지 점검이 논증을 떠받친다. 첫째, 아무 인수분해나 하나 잡아 평행사변형을 실제로 다시 만들어, 격자점이면서 제1사분면 안에 놓이고 넓이도 맞는지 확인한다. 그러지 않으면 대응하는 도형이 없는 삼중쌍까지 세게 된다. 둘째, 한 평행사변형이 서로 다른 두 삼중쌍으로 두 번 세어지지 않는지, 특히 B 와 D 의 역할이 뒤바뀔 수 없는지 확인한다. 이 두 점검을 마친 뒤에야 순서쌍의 개수가 평행사변형의 개수가 되고, 그 개수는 소수 하나씩 따로 세면 끝난다.

1STEP 1

A 옆의 두 꼭짓점에 이름 붙이기

매개변수 둘이 원점 옆 꼭짓점을 나타낸다.

B=(s,s), D=(t,kt), s,t ∈ {1,2,3,…}, k ∈ {2,3,4,…}

2STEP 2

넓이를 식 하나로 바꾸기

넓이가 세 정수의 곱 하나가 된다.

[ABCD]=2 [ABD]=| x_B y_D-x_D y_B |=|s · kt-t · s|=(k-1)st=1,000,000

3STEP 3

모든 삼중쌍이 진짜 도형이 되는지 확인

모든 삼중쌍이 진짜 도형을 만든다.

mst=10⁶, k=m+1 ⟹ A=(0,0), B=(s,s), C=(s+t,s+kt), D=(t,kt), [ABCD]=mst=10⁶

4STEP 4

같은 도형을 두 번 세지 않는지 확인

어떤 도형도 두 번 세어지지 않는다.

D 가 y=x 위에 있음 ⇔ kt=t ⇔ k=1 (k ＞ 1 이므로 불가능)

5STEP 5

소수별로 세기를 쪼개기

세기가 소수별로 나뉜다.

m=2^a₁₅^b₁, s=2^a₂₅^b₂, t=2^a₃₅^b₃, a₁+a₂+a₃=6, b₁+b₂+b₃=6

6STEP 6

6을 셋으로 나누기: 28 가지

각 소수가 28가지를 보탠다.

Σ_a₁=0⁶ (7-a₁)=7+6+5+4+3+2+1=28=C(8, 2)

7STEP 7

두 소수의 세기를 곱하기

곱하면 784, 보기 (D).

28 × 28 = 784

정답

784

삼중쌍을 한꺼번에 세는 대신 k 로 묶어 다시 세어 보자. m = k-1은 10⁶의 약수여야 하고, 각 m 에 대해 st = 10⁶/m 인 쌍 (s,t)의 개수는 약수의 개수 τ (10⁶/m) 다. 모든 m 에 대해 더하면 Σ_n ∣ 10⁶ τ(n)이고, τ (2^i5^j) = (i+1)(j+1) 이므로 이 합은 (Σ_i=0⁶(i+1))(Σ_j=0⁶(j+1)) = 28 · 28 = 784로 인수분해된다. 장부를 다르게 정리해도 같은 값이다. 작은 넓이로 손으로 확인해도 방법이 살아남는다. 1,000,000 대신 12로 바꾸면 (k-1)st = 2² · 3이고, 공식은 C(4, 2)·C(3, 2) = 6 · 3 = 18을 예측하는데, 곱이 12 인 삼중쌍을 모두 적어 보면 정확히 18 개이며 각각 서로 다른 그림을 준다. 크기도 그럴듯하다. 784는 기울기만 센 49와, s 와 t 를 남은 인수와 상관없이 마음대로 고를 수 있다면 나왔을 49 · 49 = 2401 사이에 놓인다.

💡핵심 정리

도형이 몇 개의 자연수로 완전히 정해진다면 도형 대신 숫자를 세면 된다. 단, 모든 숫자 조합이 정말 정당한 도형을 그리는지, 그리고 같은 도형이 두 번 그려지지 않는지 먼저 확인한 다음에.

A 옆의 두 꼭짓점에 이름 붙이기
넓이를 식 하나로 바꾸기
모든 삼중쌍이 진짜 도형이 되는지 확인
같은 도형을 두 번 세지 않는지 확인
소수별로 세기를 쪼개기
6을 셋으로 나누기: 28 가지
두 소수의 세기를 곱하기