AMC 10 · 2006 · #22

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
Two farmers agree that a pig is worth 300 dollars and a goat is worth 210 dollars. A debt is settled by handing over pigs or goats, with change received back in goats or pigs as needed, so each kind of animal can be given (a positive count) or received (a negative count), and only whole animals change hands. For example, a 390 dollar debt is paid with two pigs given and one goat received in change. What is the smallest positive debt that can be settled exactly this way?

Pick an answer.

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

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

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

Let p be the net pigs and g the net goats handed over, negative when received as change; the debt settled is 300p + 210g.

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

Pull out the shared factor for a floor

Both prices share a factor: 300 = 30 × 10 and 210 = 30 × 7, so 300p + 210g = 30(10p + 7g) and every settleable debt is a multiple of 30.

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

Show the floor is reachable

Reach 30 itself: 10 and 7 share no factor, so 10p + 7g = 1 works; p = -2, g = 3 is three goats given, two pigs back: 630 - 600 = 30.

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

Combine floor and reachability

Every debt is a multiple of 30 and 30 is actually reachable, so the smallest positive debt is 30 dollars, 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.