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

Latest revision as of 02:13, 8 August 2022

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?

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

Solution 1 (Diophantine Equation)

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. Bezout's Lemma tells us that the smallest $c$ for the Diophantine equation $am + bn = c$ to have solutions is when $c$ is the GCD (greatest common divisor) of $a$ and $b$ . Therefore, the answer is $gcd(300,210)=\boxed{\textbf{(C) }30}.$

Solution 2 (Divisibility Analysis)

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$ . Since we want the smallest integer, we can suppose that the answer is $30$ and go on from there. Note that three goats minus two pigs gives us $630 - 600 = 30$ exactly. Since our supposition can be achieved, the answer is $\boxed{\textbf{(C) }30}$ .

Solution 3 (Simplifying the Problem)

Let us simplify this problem. Dividing by $30$ , we get a pig to be: $\frac{300}{30} = 10$ , and a goat to be $\frac{210}{30}= 7$ . It becomes evident that if you exchange $5$ pigs for $7$ goats, we get the smallest positive difference - $5\cdot 10 - 7\cdot 7 = 50-49 = 1$ , since we can't make a non-integer with a linear combination of integers. Since we originally divided by $30$ , we need to multiply again, thus getting the answer $1\cdot 30 = \boxed{\textbf{(C) }30}$ .

2006 AMC 12A (Problems • Answer Key • Resources)
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 (Problems • Answer Key • Resources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

@@ Line 1: / Line 1: @@
+{{duplicate|[[2006 AMC 12A Problems|2006 AMC 12A #14]] and [[2006 AMC 10A Problems/Problem 22|2006 AMC 10A #22]]}}
 == Problem ==
 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>
+<math> \textbf{(A) } 5\qquad \textbf{(B) } 10\qquad \textbf{(C) } 30\qquad \textbf{(D) } 90\qquad \textbf{(E) }  210</math>
+==Solution 1 (Diophantine Equation)==
+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. ''<math>p</math>'' and ''<math>g</math>'' must be integers, which makes the equation a [[Diophantine equation]].  [[Bezout%27s Lemma]] tells us that the smallest <math>c</math> for the Diophantine equation <math>am + bn = c</math> to have solutions is when <math>c</math> is the GCD ([[greatest common divisor]]) of <math>a</math> and <math>b</math>. Therefore, the answer is <math>gcd(300,210)=\boxed{\textbf{(C) }30}.</math>
-== Solution ==
+==Solution 2 (Divisibility Analysis)==
-We see that any amount of debt can be expressed as follows:
+Alternatively, note that <math>300p + 210g = 30(10p + 7g)</math> is divisible by <math>30</math> no matter what <math>p</math> and <math>g</math> are, so our answer must be divisible by <math>30</math>. Since we want the smallest integer, we can suppose that the answer is <math>30</math> and go on from there. Note that three goats minus two pigs gives us <math>630 - 600 = 30</math> exactly.  Since our supposition can be achieved, the answer is <math>\boxed{\textbf{(C) }30}</math>.
-(300x+210y)-(300a+210b) = m > 0.
-Rearranging the terms, we have:
+==Solution 3 (Simplifying the Problem)==
-(x-a) + 210(y-b) = m.
-From here, we note that (x-a) and (y-b) can be any integer.
+Let us simplify this problem.  Dividing by <math>30</math>, we get a pig to be:  <math>\frac{300}{30} =  10</math>, and a goat to be <math>\frac{210}{30}= 7</math>.
-Thus, we let A = (x-a) and B = (y-b).
+It becomes evident that if you exchange <math>5</math> pigs for <math>7</math> goats, we get the smallest positive difference - <math>5\cdot 10 - 7\cdot 7 = 50-49 = 1</math>, since we can't make a non-integer with a linear combination of integers.
-The equation therefore becomes:
+Since we originally divided by <math>30</math>, we need to multiply again, thus getting the answer  <math>1\cdot 30 = \boxed{\textbf{(C) }30}</math>.
-A + 210B = m, where me intend to minimize the value of m.
-Dividing each side of the equation by the coefficients' GCD, we get the following:
-A + 7B = m/30.
-Since we know that A and B must be integers, we observe that m/30 must also be an integer (positive due to the constraint of the problem). Thus, the smallest possible value m can hold is 30.
-However, we must check that the equation can be satisfied when m = 30.
-We can easily see that A = -1 and B = 3 satisfy the equation.
-Thus, m = 30 is the smallest possible positive debt that can be resolved.
 == See also ==
-* [[2006 AMC 12A Problems]]
+Bezout's Lemma:
-*[[2006 AMC 12A Problems/Problem 13|Previous Problem]]
-*[[2006 AMC 12A Problems/Problem 15|Next Problem]]
+https://brilliant.org/wiki/bezouts-identity/
+{{AMC12 box|year=2006|ab=A|num-b=13|num-a=15}}
+{{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}}
+{{MAA Notice}}
 [[Category:Introductory Number Theory Problems]]

Page

Toolbox

Search