Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎See also: gr.. forgot how to count)
Line 6: Line 6:
  
 
== Solution ==
 
== Solution ==
−
We see that any amount of debt can be expressed as follows:
+
== Solution ==
−
(300x+210y)-(300a+210b) = m > 0.
+
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. ''p'' and ''g'' must be [[integer]]s, which makes the equation a [[Diophantine equation]]. The [[Euclidean algorithm]] tells us that there are integer solutions to the Diophantine equation <math>am + bn = c</math>, where <math>c</math> is the [[greatest common divisor]] of <math>a</math> and <math>b</math>, and no solutions for any smaller <math>c</math>. Therefore, the answer is the greatest common divisor of 300 and 210, which is 30, <math>\mathrm{(C) \ }</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.
+
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 give us <math>630 - 600 = 30</math> exactly. Since our theoretical best can be achived, it must really be the best, and the answer is <math>\mathrm{(C) \ }</math>.
−
Thus, we let A = (x-a) and B = (y-b).
+
debt that can be resolved.
−
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 (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 ==
 
== See also ==

Revision as of 20:40, 11 April 2007

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$ (Error compiling LaTeX. Unknown error_msg)

Solution

Solution

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. The Euclidean algorithm tells us that there are integer solutions to the Diophantine equation $am + bn = c$, where $c$ is the greatest common divisor of $a$ and $b$, and no solutions for any smaller $c$. Therefore, the answer is the greatest common divisor of 300 and 210, which is 30, $\mathrm{(C) \ }$


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

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_12A_Problems/Problem_14&oldid=14520"