2015 AMC 10B Problem 15

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

Every "$k$ of these for each of those" sentence chains the counts to a single free variable, so the total is a linear combination $13h + 5c$ of two parameters. Deciding which numbers are representable is a small Diophantine check, and because one coefficient is $5$, only the last digit of $T - 13h$ matters, which makes the test fast. Note the people-to-duck ratio is applied to people, not horses, giving $9h$ ducks.

• Building the total from the wrong ratios, e.g. 3 horses per person or 3 ducks per horse, which changes 13h + 5c to some other form.
• Stopping the search too early: $61$ needs $h = 2$ and $59$ needs $h = 3$, so checking only $h = 0, 1$ wrongly eliminates them.