Posted by George on .
Cats cost $1, dogs cost $15, and mice cost only $0.25. I want a herd of 100 animals, and I have $100, so being a cat lover, it's tempting to get only cats and mice. But I also want a dog, and my cat(s) want mice to "play" with, so the numbers of dogs, cats and mice are each positive. And no cash left over. What's the solution?

Math  Linear algebra 
tchrwill,
C = cats
D = dogs
M = mice
1(C) + 15D + .25M = 100 or
4C + 60D + M = 400 (1)
Also, C + D + M = 100 (2)
Subtracting (1) from (2) yields 3C + 59D = 300
Dividing through by the lowest coefficient yields
C + 19D + 2D/3 = 100
Let 2D/3 = an integer "k" making D = 3k/2
Substituting, 3C + 88.5k = 300 yielding C = 100  29.5k
"k" must be even and can only be 2 making C = 100  59 = 41 from which D = 3 and m = 56.
41 + 45 + 14 = 100 animals
41(1) + 45(15) + 56/4 = $100 
Math  Linear algebra 
MathMate,
Another way:
Will use the same notations, C,D and M for cats, dogs and mice, and with the same constraints where C,D and M must be integers.
From the cost,
C+15D+M/4=100....(1)
from the number of animals,
C+D+M = 100......(2)
(1)(2)
14D=(3/4)M, or
56D=3M
Since 56 and 3 are coprime, we can only have 3 dogs, 56 mice, or any multiple thereof.
However, 6 dogs and 112 mice would exceed the budget, so we go with
3 dogs, 56 mice, and are left with 41 cats.
Check:
3+56+41=100
3*15+56/4+41=100
So the solution is correct. 
Math  Linear algebra 
George,
Thank you, that was the answer I got too, but in a slightly different method, but I want to learn for how you figure this out, with this problem. I feel like you just you the same method but I am having a little problem with this one:
"Suppose you want to make $5 using exactly 100 common US coins.Easy, you say: just use nickels (5 cents each). But I say, no  we have NO nickels, only pennies (1 cent), dimes (10 cents) and quarters (25 cents)  is it possible to make $5 now with exactly 100 of these coins? Why or why not?" 
Math  Linear algebra 
MathMate,
These problems belong to a class called diophantine equations. If these are what you are doing in class, they will be solved in a different way.
For linear algebra, I will solve it similar to the previous problem, as follows.
Let integers
p=number of pennies
d=number of dimes
q=number of quarters
then again,
p+10d+25q=500...(1) (number of cents)
p+d+q=100 ....(2) (number of coins)
Subtract (2) from (1),
9d+24q=400 or
3d+8q = 400/3 ...(3)
It is evident that (3) has no solution in integers because we cannot have the sum of two integers to be a mixed fraction.