Skip to main content

2006 AMC 12A Problem 14

Problem 14 of 25IntermediateNumber Theory

Two farmers agree that pigs are worth $300\$300 and that goats are worth $210.\$210. When one farmer owes the other money, he pays the debt in pigs or goats, with “change” received in the form of goats or pigs as necessary. (For example, a $390\$390 debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?

Answer choices

Show solution

Solution

A debt DD is resolvable if and only if D=300p+210gD = 300p + 210g =30(10p+7g)= 30(10p + 7g) for integers p,g.p, g. Thus DD is a multiple of gcd⁡(300,210)=30,\gcd(300, 210) = 30, so no smaller positive debt works. A debt of $30\$30 is achievable since 30=300(−2)+210(3),30 = 300(-2) + 210(3), i.e. give 33 goats and receive 22 pigs in change. Thus, the correct answer is C.

More practice

Concepts: greatest common divisor · Diophantine Equation

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.