2006 AMC 10A Problem 22

A debt $D$ can be settled exactly when $D = 300p + 210g$ for some integers $p$ and $g$, where a negative count means that animal is handed back as change.

Lower bound: $300 = 30 \cdot 10$ and $210 = 30 \cdot 7$, so $300p + 210g = 30(10p + 7g)$ is always a multiple of $30$. The smallest positive debt is therefore at least $30$.

Achievability: we need $10p + 7g = 1$. Trying small values, $p = -2$, $g = 3$ works: $3 \cdot 210 - 2 \cdot 300 = 630 - 600 = 30$. In words, the debtor hands over three goats and receives two pigs in change.

So $30$ is both a lower bound and attainable.

The answer is $\boxed{\textbf{(C)}\ 30}$.

The set of values $ax + by$ with integer $x, y$ is exactly the set of multiples of $\gcd(a, b)$; this is Bezout's identity. The two halves of the argument mirror that theorem: the gcd divides every combination (bound), and some combination equals the gcd (construction). "Change" in the story is what allows negative coefficients.

Scale down by $30$: pigs are worth $10$, goats $7$. Since $5 \cdot 10 - 7 \cdot 7 = 1$, every integer is reachable in these units, so every multiple of $30$ dollars is a settleable debt and $30$ is the smallest positive one.

• Answering a small number like $10$ or $5$ without checking that every $300p + 210g$ is a multiple of $30$, or thinking the debt must be a whole animal ($210$).
• Computing the gcd wrongly (e.g. $90$ from $300 - 210$) or using only positive numbers of animals, which would make $210$ the smallest.