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

(Problem)
(31 intermediate revisions by 17 users not shown)
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 ==
 
== 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?
 
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> \mathrm{(A) \ } 5\qquad \mathrm{(B) \ } 10\qquad \mathrm{(C) \ } 30\qquad \mathrm{(D) \ } 90\qquad \mathrm{(E) \ }  210</math>
 +
 
 +
==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. ''<math>p</math>'' and ''<math>g</math>'' must be [[integer]]s, which makes the equation a [[Diophantine equation]].  Bezout’s Identity 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 [[greatest common divisor]] of <math>a</math> and <math>b</math>. Therefore, the answer is <math>gcd(300,210)</math>, which is <math>30</math>, <math>\mathrm{(C) \ }</math>
 +
 
 +
==Solution 2==
 +
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 gives 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>.
 +
 
 +
==Solution 3==
  
== Solution ==
+
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>.  
We see that any amount of debt can be expressed as follows:
+
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 made a non-integer with a linear combination of integers.
(300x+210y)-(300a+210b) = m > 0.
+
Since we originally divided by <math>30</math>, we need to multiply again, thus getting the answer:  <math>1\cdot 30 = \mathrm{(C) 30}</math>
Rearranging the terms, we have:
 
300(x-a) + 210(y-b) = m.
 
From here, we note that (x-a) and (y-b) can be any integer.
 
Thus, we let A = (x-a) and B = (y-b).
 
The equation therefore becomes:
 
300A + 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:
 
10A + 7B = m/30.
 
Since we know that A and B must be integers, we observe that m/30 must also be an integer. 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 ==
 
== See also ==
* [[2006 AMC 12A Problems]]
+
Bezout's Identity:
*[[2006 AMC 12A Problems/Problem 13|Previous Problem]]
+
 
*[[2006 AMC 12A Problems/Problem 15|Next Problem]]
+
https://artofproblemsolving.com/wiki/index.php/Bezout%27s_Lemma
 +
 
 +
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]]
 
[[Category:Introductory Number Theory Problems]]

Revision as of 20:11, 1 May 2021

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

Solution 2

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 gives us $630 - 600 = 30$ exactly. Since our theoretical best can be achieved, it must really be the best, and the answer is $\mathrm{(C) \ }$.

Solution 3

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 made 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 = \mathrm{(C) 30}$

See also

Bezout's Identity:

https://artofproblemsolving.com/wiki/index.php/Bezout%27s_Lemma

https://brilliant.org/wiki/bezouts-identity/

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

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