h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I was asked if I could figure this one out, and so far I don't have the slightes idea. It does not appear too difficult at first, but... you will see:

"You have to buy some animals. More to the point, you have to buy exactly one hundred (100) animals. And, you have to spend exactly one hundred (100) Euros. The prices are:
1 Euro for a four-pack of mice.
1 Euro for a cat.
15 Euros for a dog.
Unfortunately, you cannot simply buy 100 cats, because it is one of the specifications of this riddle that you have to have at least one animal of each kind (which means, of course, that you will end up at least four mice as mice only come in four-packs).
How many dogs, cats and mice will you have to buy to meet the requirements? Remember, you have to buy no more and no less than 100 animals, and you have to spend no more and no less than 100 Euros."

I don't know if this is actually possible. So I have a number of questions. First, can such a problem be solved? Do you have to either manually or with the help of a computer program go through all the possible combinations, or is there a formula that takes in all the variables? If so, what is that formula? Second, can this specific problem be solved? Is there a combination of cats, mice and dogs that results in 100 animals for one hundred Euros?

Have fun racking your brains over this one...

Y.

This sort of puzzle can generally be solved by a combination of trial and error and a little bit of logic. The analytical approach of writing out equations for everything doesn't work well because traditional equations allow the variables to be any real number, whereas in this case the solution must be in whole numbers.

Equations involving whole numbers are called Diophantine equations. There's an entry on them in the Guide. But they are tricky little critters and you're better off fiddling around with what you're given.

Let's see.

100/15 = 6.667 so we can have at most 6 dogs.

If we had 6 dogs, then we would have paid €90, which means that we would have only €10 left to buy 94 animals. Not possible.

If we had 5 dogs, then we would have €25 left to buy 95 animals.
- Buying 24 4-packs of mice would be 96 mice, too many.
- Buying 23 4-packs of mice would be 92 mice. We still have €2 to buy 3 more animals. Not possible.
- Buying 22 4-packs of mice would be 88 mice. We need 7 more animals and have only €3 to do it. So obviously there is no combination of mice and cats that will have 95 animals with €25. So it can't be 5 dogs.

Keep going in this vein and we should soon arrive at a solution.

Actually, there is a better approach using equations. It still involves fiddling.

Let d = number of dogs, c = number of cats, m = number of mouse 4-packs

Then d + c + 4m = 100 (number of animals)
and 15d + c + m = 100 (price of animals)

Since both these equal 100, they equal each other so:

d + c + 4m = 15 + c + m

or

14d = 3m

Now d and m are whole numbers, and 3 and 14 share no factors. So d must be a multiple of 3 and m must be a multiple of 14. We already know d can't be greater than 4 so it must be 3.

With 3 dogs at €15 each, there is €85 left to buy 97 animals. m has to be a multiple of 14 so it can be 14, 28, 42 etc:

m = 14; 56 mice at €14. €71 left to by 41 cats.
m = 28; 102 mice. Too many.

This suggest to me that there is no solution to the original problem.

Or that I've made a mistake.

I'm a bit rusty but:
Let M be he number of packs of mice, D the number of dogs, and C the number of cats we buy.
Thus a satisfactory solution has:
15D + C + M = 100 (and so we have spent 100 euro).
Also
D + C + 4M = 100 (and so we have 100 animals).
Thus in the satisfactory solution we can represent C as
C = 100 - M - 15D
ANd replace C in the second equation with this expression
D + (100 - M - 15D) + 4M = 100
Or
D + 100 - M - 15D + 4M = 100
OR, equivalently
3M - 14D = 0
or
3M = 14D
So - wherever we buy fourteen-thirds as many dogs as we do mice, this will satisfy.
This is fine for a linear solution, but since we require both M and D to be integer (whole) number, we can see at a glance there is no satisfactory solution

Ah, shoot.
Fair enough, Gnomon.

I guess our educations covered much of the same ground...

I did make a mistake.

14d = 3m means that d must be a multiple of 3, m must be a multiple of 14

d can't be 6 or greater, so it must be 3. m can't be > 25 because 25x4 = 100. so m must be 14.

3 dogs at €15 each is €45.
14 mouse packs at €1 each is €14 and contains 56 mice.

That's 59 animals costing €59. We can make up the difference in cats: 41 cats.

So three dogs, 14 packs of mice and 41 cats will do the trick! Great work, and thank you all.

I, myself, was lost, however, at how you arrived at the
"d + c + 4m = 15 + c + m
or
14d = 3m"
equation.

Starting at "d+c+4m=15+c+m", I only get this far:
d+c+4m=15+c+m ----- SUBSTRACT c
d+4m=15+m ----- SUBSTRACT 4m
d=15-3m ----- then what? DIVIDE BY d, maybe? But that would only give me
1=(15-3m)/d ----- and I am not sure that this helps me much.

So how did you get there? Or rather: what steps am I missing/ where did you lose me?

Y.

You've written d + c + 4m = 15 + c + m but you've left out a "d".

It is:

d + c + 4m = 15d + c + m

There's a c on both sides so you can just throw them away. Or to be really pedantic, you can subtract c from both sides and it will still be equal. So:

d + 4m = 15d + m

Now you can move the d from one side to the other changing its sign. Or the pedantic way is to subtract d from each side to get:

4m = 14d + m

Now do the same with m:

3m = 14d

That's all standard mathematics of the sort they teach in school. The next bit isn't taught in schools though:

If m and d are whole numbers and 3m = 14d, then m must be a multiple of 14 and d must be a multiple of 3. Think about it hard enough and you'll figure it out.

After that it is plain sailing.