Difference between revisions of "2006 AMC 12A Problems/Problem 14"
m (dollar signs ...) |
(→See also: remove extra template) |
||
| Line 12: | Line 12: | ||
== See also == | == See also == | ||
| − | |||
{{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}} | {{AMC10 box|year=2006|ab=A|num-b=21|num-a=23}} | ||
[[Category:Introductory Number Theory Problems]] | [[Category:Introductory Number Theory Problems]] | ||
Revision as of 17:14, 1 December 2007
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
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. 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 
, where 
is the greatest common divisor of 
and 
, and no solutions for any smaller . Therefore, the answer is the greatest common divisor of 300 and 210, which is 30, 
Alternatively, note that 
is divisible by 30 no matter what and are, so our answer must be divisible by 30. In addition, three goats minus two pigs give us 
exactly. Since our theoretical best can be achived, it must really be the best, and the answer is .
debt that can be resolved.
See also
| 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 | ||
