AMC 10 · 2006 · #14

학년 7 number-theory
유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint
linear-diophantinegcdprime-factorization convert-to-algebra ↑ 선수 지식: linear-diophantinegcd
📏 긴 풀이 💡 3 개 인사이트
문제
한 마리에 300원인 돼지와 210원인 염소로 빚을 갚고, 거스름은 다른 동물로 받을 수 있다. 이런 교환으로 정확히 갚을 수 있는 가장 작은 양의 빚을 구하여라.

답을 골라 클릭하세요.

(A)
5
(B)
10
(C)
30
(D)
90
(E)
210
풀이 과정
전략 변수 도입하기

돼지와 염소의 수가 정해져 있지 않으므로 도구 #4(변수 도입하기)로 이름을 붙인다: 돼지의 순 개수를 p, 염소의 순 개수를 g 라 하고, 음수는 그 동물이 거스름으로 돌아옴을 뜻한다. 그러면 갚을 수 있는 모든 빚은 300p + 210g 이다. 도구 #7(작은 문제로 쪼개기)은 질문을 더 깔끔한 두 조각으로 나눈다: 먼저 어떤 빚도 내려갈 수 없는 바닥을 찾고, 그다음 그 바닥에 실제로 도달할 수 있는지 확인한다. 바닥은 300과 210이 공유하는 공약수에서 나오고, 도달은 정수를 찾는 작은 도구 #6(추측하고 확인하기) 탐색으로, 거스름을 음수로 모델링해 해결한다. 도달 가능한 바닥이 바로 가장 작은 양의 빚이다.

1STEP 1

부호 있는 개수로 빚 모델링하기

부호 있는 개수가 거스름을 음수로 나타내게 해 준다.

빚 = 300p + 210g, p, g ∈ Z
2STEP 2

공약수를 빼내 바닥 만들기

공약수 때문에 갚을 수 있는 빚이 모두 30의 배수가 된다.

300p + 210g = 30(10p + 7g) → 빚은 30 의 배수
3STEP 3

바닥에 도달할 수 있음 보이기

구체적인 교환이 정확히 30에 도달한다.

10(-2) + 7(3) = 1 → 300(-2) + 210(3) = 30
4STEP 4

바닥과 도달 가능성 합치기

도달 가능한 바닥이 최솟값이므로 답은 30, 보기 (C).

min{300p + 210g ＞ 0} = 30 → (C)
정답
30
답 30은 두 가격 모두를 나눠야 하는데, 실제로 그렇다: 300 = 30 × 10, 210 = 30 × 7. 주어진 예에도 맞는다. 390 = 30 × 13으로 30의 배수이기 때문이다. 오답 선택지는 바닥 검사를 통과하지 못한다: 5(A)와 10(B)은 30 보다 작지만 어떤 빚도 30 바닥을 이길 수 없으므로 불가능하고, 90(D)은 갚을 수 있지만(300 - 210, 돼지 한 마리를 주고 염소 한 마리를 받음) 30 × 3으로 최소가 아니며, 210(E)은 염소 한 마리 값일 뿐 최소와는 거리가 멀다. 오직 30 만이 도달 가능하면서 이길 수 없다.
💡핵심 정리

거스름까지 주고받을 수 있으면, 갚을 수 있는 모든 금액은 두 가격의 최대공약수의 배수가 되므로, 가장 작은 빚은 그 최대공약수 자체다: 여기서는 gcd(300, 210) = 30.

  • 부호 있는 개수로 빚 모델링하기
  • 공약수를 빼내 바닥 만들기
  • 바닥에 도달할 수 있음 보이기
  • 바닥과 도달 가능성 합치기

비슷한 유형 더 풀어보기

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