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

(creation)
m (Reverted edits by Temperal (Talk); changed back to last version by Azjps)
 
Line 1: Line 1:
== Problem ==
+
#redirect [[2006 AMC 12A Problems/Problem 14]]
 
 
Two farmers agree that pigs are worth <math>300</math> dollars and that goats are worth <math>210</math> dollars. 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 <math>390</math> dollar 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</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>.
 
debt that can be resolved.
 
 
 
== See also ==
 
{{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}}
 
 
 
[[Category:Introductory Number Theory Problems]]
 

Latest revision as of 21:25, 1 December 2007