Difference between revisions of "2006 AMC 12A Problems/Problem 14"

(Solution)
(Solution)
Line 8: Line 8:
  
 
== Solution ==
 
== Solution ==
 +
 +
Solution 1:
 +
 
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>
 
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 achieved, it must really be the best, and the answer is <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 achieved, it must really be the best, and the answer is <math>\mathrm{(C) \ }</math>.
 
debt that can be resolved.
 
debt that can be resolved.
 +
 +
Solution 2:
 +
 +
Let us think of it as if the farmers would like to pay off a certain debt, then the farmers take turns giving each other goats and pigs until it is resolved. Let us suppose they start at 0 debt, and they want to get to the smallest debt possible. Each time a pig or goat is exchanged, the remainder of the debt when divided by 30 stays the same. This is because a goat and pig are both worth multiples of 30. Since the debt is positive, the smallest possible achievable debt is 30 (C).
  
 
== See also ==
 
== See also ==

Revision as of 13:19, 22 February 2011

The following problem is from both the 2006 AMC 12A #14 and 2006 AMC 10A #22, so both problems redirect to this page.

Problem

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

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

Solution

Solution 1:

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 achieved, it must really be the best, and the answer is $\mathrm{(C) \ }$. debt that can be resolved.

Solution 2:

Let us think of it as if the farmers would like to pay off a certain debt, then the farmers take turns giving each other goats and pigs until it is resolved. Let us suppose they start at 0 debt, and they want to get to the smallest debt possible. Each time a pig or goat is exchanged, the remainder of the debt when divided by 30 stays the same. This is because a goat and pig are both worth multiples of 30. Since the debt is positive, the smallest possible achievable debt is 30 (C).

See also

2006 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 13
Followed by
Problem 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions
2006 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 21
Followed by
Problem 23
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 10 Problems and Solutions
Invalid username
Login to AoPS