Difference between revisions of "2006 AMC 10A Problems/Problem 22"

m (See also: +box)
m (redirect amc 12 q)
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]]
 

Revision as of 17:44, 28 October 2007