2015 AMC 10B Problem 15

P11-15~4 minPrint

Diophantine Equations Linear Equations & Word Problems Use the answer choices (mod checks, size, form) to eliminate or select Organized listing / direct enumeration

The town of Hamlet has $3$ people for each horse, $4$ sheep for each cow, and $3$ ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?

Show solution without answering

Key insight

With h horses and c cows the total is 13h + 5c. Take 13s away from each choice and look for a multiple of 5.

Solution

1. Count everything using horses and cows. Say there are $h$ horses and $c$ cows.
- $3$ people per horse gives $3h$ people.
- $3$ ducks per person gives $3 \cdot 3h = 9h$ ducks.
- $4$ sheep per cow gives $4c$ sheep.
2. Add them up.
$h + 3h + 9h + c + 4c = 13h + 5c.$
So the total is some number of $13$ s plus some number of $5$ s.
3. Test each choice. Take away $13$ zero, one, two or more times, and see whether what is left is a multiple of $5$ (ends in $0$ or $5$ ):

Total	Take away $0, 13, 26, 39$	Works?
$41$	$41, 28, 15$	yes: $15 = 5 \cdot 3$ , so $h = 2$ , $c = 3$
$47$	$47, 34, 21, 8$	no: none ends in $0$ or $5$
$59$	$59, 46, 33, 20$	yes: $h = 3$ , $c = 4$
$61$	$61, 48, 35$	yes: $h = 2$ , $c = 7$
$66$	$66, 53, 40$	yes: $h = 2$ , $c = 8$

For $47$ we cannot take away more $13$ s, because $47 - 52$ is negative.

The only total that cannot happen is $47$ .

The answer is $\boxed{\textbf{(B)}\ 47}$ .

Why this works

Each "so many of these for each of those" fact ties one count to another, so the whole town depends on just two numbers, horses and cows. The total becomes $13h + 5c$ . Because one of the numbers is $5$ , checking a total only needs its last digit after taking away $13$ s, which makes the test quick.

Concise solution

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

Let there be $h$ horses and $c$ cows. Then there are $3h$ people, $3 \cdot 3h = 9h$ ducks, and $4c$ sheep. The total is
$h + 3h + 9h + c + 4c = 13h + 5c,$
where $h$ and $c$ are non-negative integers.

A total $T$ is possible exactly when $T - 13h$ is a non-negative multiple of $5$ for some $h$ . Since only the last digit matters for divisibility by $5$ , subtract $0, 13, 26, 39, \dots$ and look for a result ending in $0$ or $5$ :

$41$ : $41 - 26 = 15$ . Possible ( $h = 2$ , $c = 3$ ).
$47$ : $47, 34, 21, 8$ — none ends in $0$ or $5$ . Impossible.
$59$ : $59 - 39 = 20$ . Possible.
$61$ : $61 - 26 = 35$ . Possible.
$66$ : $66 - 26 = 40$ . Possible.

The answer is $\boxed{\textbf{(B)}\ 47}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 7: Algebra With Integers
Introduction to Algebra, Chapter 3: One-Variable Linear Equations (§3.3, §3.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Algebra, Chapter 11: Special Factorizations (§11.5)