Difference between revisions of "2006 AMC 12A Problems/Problem 14"
(→Solution 3) |
m (→Solution 3) |
||
(14 intermediate revisions by 6 users not shown) | |||
Line 5: | Line 5: | ||
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> \ | + | <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 2 (Divisibility Analysis)== | |
+ | 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>. | ||
− | + | ==Solution 3 (Simplifying the Problem)== | |
− | |||
− | |||
− | |||
− | |||
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>. | 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>. | ||
− | 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 | + | 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. |
− | Since we originally divided by <math>30</math>, we need to multiply again, thus getting the answer | + | 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>. |
== See also == | == See also == | ||
+ | Bezout's Lemma: | ||
+ | |||
+ | https://brilliant.org/wiki/bezouts-identity/ | ||
+ | |||
{{AMC12 box|year=2006|ab=A|num-b=13|num-a=15}} | {{AMC12 box|year=2006|ab=A|num-b=13|num-a=15}} | ||
{{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}} | {{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}} |
Latest revision as of 03: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.
Contents
Problem
Two farmers agree that pigs are worth dollars and that goats are worth
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
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?
Solution 1 (Diophantine Equation)
The problem can be restated as an equation of the form , where
is the number of pigs,
is the number of goats, and
is the positive debt. The problem asks us to find the lowest x possible.
and
must be integers, which makes the equation a Diophantine equation. Bezout's Lemma tells us that the smallest
for the Diophantine equation
to have solutions is when
is the GCD (greatest common divisor) of
and
. Therefore, the answer is
Solution 2 (Divisibility Analysis)
Alternatively, note that is divisible by
no matter what
and
are, so our answer must be divisible by
. Since we want the smallest integer, we can suppose that the answer is
and go on from there. Note that three goats minus two pigs gives us
exactly. Since our supposition can be achieved, the answer is
.
Solution 3 (Simplifying the Problem)
Let us simplify this problem. Dividing by , we get a pig to be:
, and a goat to be
.
It becomes evident that if you exchange
pigs for
goats, we get the smallest positive difference -
, since we can't make a non-integer with a linear combination of integers.
Since we originally divided by
, we need to multiply again, thus getting the answer
.
See also
Bezout's Lemma:
https://brilliant.org/wiki/bezouts-identity/
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.