2006 AMC 10A Problems/Problem 22

Problem

Two farmers agree that pigs are worth $300 and that goats are worth $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 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?

$\mathrm{(A) \ } $5\qquad\mathrm{(B) \ } $10\qquad\mathrm{(C) \ } $30\qquad\mathrm{(D) \ } $90\qquad\mathrm{(E) \ } $210\qquad$

Solution

The problem can be restated as an equation of the form $300p + 210g = x$ , where $p$ is the number of pigs, $g$ is the number of goats, and $x$ is the positive debt. The problem asks us to find the lowest x possible. p and g must be integers, which makes the equation a Diophantine equation. The Euclidean algorithm tells us that there are integer solutions to the Diophantine equation $am + bn = c$ , where $c$ is the greatest common divisor of $a$ and $b$ , and no solutions for any smaller $c$ . Therefore, the answer is the greatest common divisor of 300 and 210, which is 30, $\mathrm{(C) \ }$

Alternatively, note that $300p + 210g = 30(10p + 7g)$ is divisible by 30 no matter what $p$ and $g$ are, so our answer must be divisible by 30. In addition, three goats minus two pigs give us $630 - 600 = 30$ exactly. Since our theoretical best can be achived, it must really be the best, and the answer is $\mathrm{(C) \ }$ .

Page

Toolbox

Search

2006 AMC 10A Problems/Problem 22

Problem

Solution

See also