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

m (Solution 2)
m (See also)
Line 23: Line 23:
  
 
== See also ==
 
== See also ==
 +
Bezout's Identity:
 +
 +
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}}
 
{{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}}

Revision as of 18:00, 17 April 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$

Solutions

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