AMC 10 · 2006 · #14

Grade 7 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint
linear-diophantinegcdprime-factorization convert-to-algebra ↑ Prerequisites: linear-diophantinegcd
📏 Long solution 💡 3 insights
Problem
A debt is settled with pigs worth 300 and goats worth 210, and change may come back in the other animal. Find the smallest positive debt such an exchange can settle exactly.

Pick an answer.

(A)
5
(B)
10
(C)
30
(D)
90
(E)
210
How to solve
Strategy Introduce a Variable

The pigs and goats have no fixed count, so Tool #4 (Introduce a Variable) names them: let p be the net number of pigs and g the net number of goats, where a negative value means that animal comes back as change. Every settleable debt is then 300p + 210g. Tool #7 (Identify Subproblems) splits the question into two cleaner pieces: first find a floor no debt can drop below, then check that the floor is actually reachable. The floor falls out of a common factor shared by 300 and 210; reaching it is a small Tool #6 (Guess and Check) search for whole numbers, using negatives to model change. A floor that is also achievable is exactly the smallest positive debt.

1STEP 1

Model the debt with signed counts

Signed counts let change be modelled as a negative number.

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

Pull out the shared factor for a floor

The shared factor forces every settleable debt to be a multiple of 30.

300p + 210g = 30(10p + 7g) → debt is a multiple of 30
3STEP 3

Show the floor is reachable

An explicit exchange reaches exactly 30.

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

Combine floor and reachability

A reachable floor is the minimum, so the answer is 30, choice (C).

min{300p + 210g ＞ 0} = 30 → (C)
Answer
30
The answer 30 must divide both prices, and it does: 300 = 30 × 10 and 210 = 30 × 7. It also fits the given example, since 390 = 30 × 13 is a multiple of 30. The distractors fail the floor test: 5 (A) and 10 (B) are smaller than 30, but no debt can beat the 30 floor, so they are impossible; 90 (D) is settleable (it equals 300 - 210, one pig given and one goat received) but it is 30 × 3, not the smallest; 210 (E) is just one goat's price, far from minimal. Only 30 is both reachable and unbeatable.
💡Key takeaway

When you can pay and also get change, every amount you can settle is a multiple of the greatest common factor of the two prices, so the smallest debt is that factor itself: here gcd(300, 210) = 30.

  • Model the debt with signed counts
  • Pull out the shared factor for a floor
  • Show the floor is reachable
  • Combine floor and reachability

More like this

Same archetype — closest grade level first.