|
|
| Line 1: |
Line 1: |
| − | == Problem ==
| + | #redirect [[2006 AMC 12A Problems/Problem 14]] |
| − | 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?
| |
| − | | |
| − | <math>\mathrm{(A) \ } \$5\qquad\mathrm{(B) \ } \$10\qquad\mathrm{(C) \ } \$30\qquad\mathrm{(D) \ } \$90\qquad\mathrm{(E) \ } \$210\qquad</math>
| |
| − | | |
| − | | |
| − | == Solution ==
| |
| − | The problem can be restated as an equation of the form <math>300p + 210g = x</math>, where <math>p</math> is the number of pigs, <math>g</math> is the number of goats, and <math>x</math> is the positive debt. The problem asks us to find the lowest ''x'' possible. ''p'' and ''g'' must be [[integer]]s, which makes the equation a [[Diophantine equation]]. The [[Euclidean algorithm]] tells us that there are integer solutions to the Diophantine equation <math>am + bn = c</math>, where <math>c</math> is the [[greatest common divisor]] of <math>a</math> and <math>b</math>, and no solutions for any smaller <math>c</math>. Therefore, the answer is the greatest common divisor of 300 and 210, which is 30, <math>\mathrm{(C) \ }</math>
| |
| − | | |
| − | | |
| − | Alternatively, note that <math>300p + 210g = 30(10p + 7g)</math> is divisible by 30 no matter what <math>p</math> and <math>g</math> are, so our answer must be divisible by 30. In addition, three goats minus two pigs give us <math>630 - 600 = 30</math> exactly. Since our theoretical best can be achived, it must really be the best, and the answer is <math>\mathrm{(C) \ }</math>.
| |
| − | | |
| − | == See also ==
| |
| − | {{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}}
| |
| − | | |
| − | [[Category:Introductory Number Theory Problems]]
| |
