2006 AMC 10A Problem 22

P21-25~4 minPrint

Diophantine Equations GCD & LCM Bound the quantity above/below or estimate to pin it down Test small/specific values or special cases to find or verify the answer

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?

Show solution without answering

Key insight

Every payment is made of 300s and 210s, added or subtracted, so it is a multiple of 30. Three goats minus two pigs makes exactly 30.

Solution

A debt can be paid if it equals (pigs handed over) $\times 300$ plus (goats handed over) $\times 210$ , where animals given back as change count as negative. This is a "smallest possible" question, so show two things: nothing smaller than $30$ works, and $30$ does work.

Part 1: every debt is a multiple of 30.

Both prices are multiples of $30$ : $300 = 30 \times 10$ and $210 = 30 \times 7$ .
Adding or subtracting multiples of $30$ always gives a multiple of $30$ . So any debt that can be settled is a multiple of $30$ , and the smallest positive one is at least $30$ .

Part 2: a debt of 30 can be settled.

3. In units of $30$ dollars, a pig is worth $10$ and a goat $7$ . We want $1$ unit. Try multiples of $7$ : $7, 14, 21, \ldots$ . The number $21$ is $1$ more than $20$ . So $3$ goats minus $2$ pigs works:
$3 \times 210 - 2 \times 300 = 630 - 600 = 30.$
4. In words: the farmer who owes $30$ dollars hands over $3$ goats and gets $2$ pigs back as change.

Nothing smaller than $30$ works, and $30$ does, so the answer is $30$ .

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

Why this works

When you can add and subtract two amounts as often as you like, the smallest positive total you can reach is their greatest common divisor. It can never be smaller, because the greatest common divisor divides everything you make, and some combination always reaches it exactly. The "change" in the story is what allows subtracting.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 7: Algebra With Integers
Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
Introduction to Algebra, Chapter 11: Special Factorizations (§11.5)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.7)