AMC 10 · 2006 · #22

학년 7 number-theory
유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint
linear-diophantinegcdprime-factorization convert-to-algebra ↑ 선수 지식: linear-diophantinegcd
📏 긴 풀이 💡 3 개 인사이트
문제
두 농부가 돼지 한 마리는 300, 염소 한 마리는 210이라고 합의한다. 빚은 돼지나 염소를 건네서 갚고, 필요하면 염소나 돼지로 거스름을 돌려받는다. 그래서 각 동물은 주는 쪽(양수 개수)일 수도, 받는 쪽(음수 개수)일 수도 있다. 또 동물은 마리 단위로만 오간다. 예를 들어 390 빚은 돼지 두 마리를 주고 염소 한 마리를 거스름으로 받아 갚는다. 이런 교환으로 정확히 갚을 수 있는 가장 작은 양의 빚은 얼마인가?

답을 골라 클릭하세요.

(A)
5
(B)
10
(C)
30
(D)
90
(E)
210

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

풀이 과정
전략 변수 도입하기

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

1STEP 1

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

돼지의 순 개수를 p, 염소의 순 개수를 g라 하자(받으면 음수). 갚는 금액은 300p + 210g다.

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

공약수를 빼내 바닥 만들기

300 = 30 × 10, 210 = 30 × 7이므로 300p + 210g = 30(10p + 7g)이고, 모든 빚은 30의 배수다.

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

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

10과 7은 서로소. p = -2, g = 3이면 10p + 7g = 1. 염소 세 마리 주고 돼지 두 마리 받으면 630 - 600 = 30.

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

바닥과 도달 가능성 합치기

모든 빚이 30의 배수이고 30에 실제로 도달하므로, 가장 작은 양의 빚은 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 · 비슷한 학년부터.