A dog costs $15, four mice cost $1 and a cat costs $1.

Somebody pointed out the obvious answer of 100 cats; I think I've seen
this problem before with the added stipulation that you must include at
least one of each animal.

The mathematical way to solve this problem is to write the total cost
of the animals as an equation.  Let d, m, and c be the numbers of dogs,
mice, and cats, respectively.  So cost = 15d + m/4 + c = 100.  Also, we
know that the total number of animals is 100: d + m + c = 100.

We have two equations in only three unknowns, but we want our variables
to all be positive (or just non-negative, depending) integers.  This
type of equation is called a Diophantine equation (or I suppose a
Diophantine system, here).  In general, there is no direct way to solve
this sort of problem in the way you can solve, say, a system of 3
linear equations in 3 variables, except for testing values, although
there are some techniques which can be applied to some problems to help
reduce the amount of searching for solutions.

Since we only have one extra degree here, we can solve it by testing
values for one variable.  Since we can't have negative or fractional
animals, clearly the number of dogs is 0, 1, 2, 3, 4, 5, or 6.  7 dogs
cost $105 -- too much.  Plug a value in for d and solve the resulting
system of two linear equations in two variables.  For d=0, we have m/4
+ c = 100, m + c = 100.  This gives the already-known answer of 0 dogs,
0 mice and 100 cats.

For d=1, we have 15 + m/4 + c = 100, 1 + m + c = 100, or m/4 + c = 85,
m + c = 99.  Solve for m by subtracting the second equation from the
first: 3m/4 = 14, m=56/3.  Since this is not a whole number, we don't
get an answer for this value of d.

Trying the other values of d we find another solution: d=3, m=56,
c=41.  For d=6 we also get a whole number of mice, m=112, but this
leaves us needing a negative number of cats.

One technique that often helps in this sort of problem is modular
arithmetic.  For a given "base" number, we consider each number as
equal to its remainder when divided by the base.  For instance, in mod
3 arithmetic, 0 = 3 = 6 = 9 = ... and 1 = 4 = 7 = ....  By taking our
two equations mod 3, we get: 15d + m/4 + c = 1 and d + m + c = 1.  The
m/4 is hard to deal with so multiply that entire equation by 4:  60d +
m + 4c = 1.  Now, apply the mod 3 to the products as well: 60d = 0d and
4c = c + 3c = c.  So we have m + c = 1 and d + m + c = 1.  This tells
us that d = 0 mod 3, or in other words, that d is divisible by 3 (which
you may have noticed in our trial-and-error solution above).

-- Joseph W. DeVincentis <devjoe@wilma.che.utexas.edu>