AMC12 2006 A

AMC12 2006 A · Q14

AMC12 2006 A · Q14. It mainly tests GCD & LCM, Diophantine equations (integer solutions).

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?

两位农民约定猪值 $300$ 美元，山羊值 $210$ 美元。当一位农民欠另一位钱时，他用猪或山羊来偿还债务，并在需要时以山羊或猪的形式收取“找零”。（例如，$390$ 美元的债务可以用两头猪支付，并收到一只山羊作为找零。）能够用这种方式结清的最小正债务金额是多少？

(A) $5$ $5$

(B) $10$ $10$

(D) $90$ $90$

(E) $210$ $210$

Answer

Correct choice: (C)

正确答案：（C）

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

该问题可重述为形如 $300p + 210g = x$ 的方程，其中 $p$ 为猪的数量，$g$ 为山羊的数量，$x$ 为正债务金额。题目要求找到可能的最小 $x$。$p$ 和 $g$ 必须为整数，因此这是一个丢番图方程。裴蜀定理告诉我们，对于丢番图方程 $am + bn = c$，使其有解的最小 $c$ 是 $a$ 与 $b$ 的最大公因数。因此答案是 $gcd(300,210)=\boxed{\textbf{(C) }30}$。

Topics