Math experts: Find an elegant solution for this Car Talk puzzler

In My Humble Opinion
1

I was just listening to an old episode of Car Talk, and they had this puzzler.

RAY: You’re given a hundred dollars and told to spend it all purchasing exactly a hundred animals at the pet store. Dogs cost $15. Cats cost a buck, and mice are 25 cents each.

TOM: Let me get this straight. You have to spend exactly a hundred bucks and you end up with exactly a hundred animals?

RAY: Right. The other only other criterion is that you have to purchase at least one of each animal.

The question is, how many of each animal do you have to purchase to equal a hundred animals purchased at exactly a hundred dollars?

I didn’t do very well in algebra when I took it in middle school more than 50 years ago, and I haven’t gotten any better at it since. When confronted by this kind of problem, I usually just use trial and error, plugging in different numbers and watching for patterns until I home in on a solution.

I ended up having to create a spreadsheet to do that this time, but I eventually found it. The whole time I was doing that, however, I was telling myself, surely there’s a simple and elegant way to solve it with math that I’m just too dumb to figure out.

So imagine my surprise when I listened to the next episode where they gave the answer, and admitted they had brute-forced it too. These two MIT grads didn’t have an algebraic answer. Here’s the page with their solution.

Surely our resident math whizzes can find a better method, right?

Answer: 3 dogs, 41 cats, 56 mice.

2

We have two equations:
0.25M + C + 15D = 100
C + D + M = 100

Multiply both by 4 to make things easier:
M + 4C + 60D = 400
4M + 4C + 4D = 400

And subtract:
56D - 3M = 0
Or:
56D = 3M

Note that 56 isn’t divisible by 3. And we must use whole numbers (no partial dogs). So D must be 3 or 6. 9 would be too much money (9*$15).

So if we try D=3, then M=56, and then to make 100 we have C=41. And we can then check that it fits the price constraint as well.

3

There’s not going to be an “elegant” solution here, as they note.

This is an example of what’s called a Diophantine problem. In this case, a linear one. In general, there are not “elegant” algebraic solutions to them. For some specific ones, there may be, but there are no general solutions.

The key to solving it is in realizing any solution must involve a whole number of animals - you aren’t going to buy a quarter of a dog or something like that. So, you do what they did - basically trial and error but in a smart way.

You know there can’t be more than 6 dogs. Likewise, you know the number of mice must be a multiple of 4.

From there, you can use some reasoning to cut down the search space but there’s still going to be a bit of guess and check, just like they said.

4

Not really. You have two equations with three unknowns:

15D + 1C + .25M = 100
D + C + M = 100

You also know that D, C, and M are all integers (don’t think you want to buy half a cat), and all are greater than 0 (can’t sell the store a dog).

If you subtract the second equation from the first, you get

14D - .75M = 0

Or

14D = .75M

Or

M = 18.666666D

OK, D has to be divisible by 3, and M has to be divisible by 4. So, try D=3, M=56… and C=41

5

Thanks to our two doctors. Looking at the Car Talk page again, it looks like Ray did exactly what @Dr.Winston_OBoogie suggested, but he just stopped short of explicitly saying he tried D=18.333M, and 2D=36.666M, and therefore 3D=56M. I got the impression that after the first two, he just tried some other method.

Thanks again. This will be a big help next time I go to the pet store.

6

I don’t need no fancy equations. You have to find a combination of a non-zero combination of dogs and mice that averages $1 and then fill in with cats. The only equation I need is 15d + m/4 = d+m which means 14d =3m/4 Since the right hand side has to be divisible by 3, so does the left hand side, so d=3 from which m=56, leaving c=41.

7

Excellent! I knew there had to be a better solution!

How strange that Tom and Ray didn’t figure it out and that no one else pointed out this method to them.

Thanks very much.

8

For fun, I fed the OP into ChatGPT to see if it would figure it out, and, somewhat to my surprise, it got it bang on. Always worth a try and do some sanity checking afterward. Its full reply, if interested:

Click to expand

This is a classic puzzle that can be solved using a system of equations. Let’s denote:

d as the number of dogs,
c as the number of cats,
m as the number of mice.

From the problem, we know two things:

  1. The total number of animals is 100:
    d + c + m = 100
  2. The total cost is $100:
    15d + c + 0.25m = 100

Additionally, you must purchase at least one of each animal, meaning d ≥ 1, c ≥ 1, and m ≥ 1.

Step-by-step approach:

We can solve this system by substitution or trial and error since d, c, and m are integers. Let’s start by manipulating the two equations.

First, solve for c from the first equation:
c = 100 - d - m

Now substitute this into the second equation:
15d + (100 - d - m) + 0.25m = 100

Simplify:
15d + 100 - d - m + 0.25m = 100

Combine like terms:
14d - 0.75m = 0

Rearrange to solve for m:
m = 14d / 0.75 = 56d / 3

For m to be an integer, d must be a multiple of 3. Let’s try different values for d.

Trying different values of d:
If d = 3:
m = (56 * 3) / 3 = 56
Substituting d = 3 and m = 56 into the first equation:
c = 100 - 3 - 56 = 41

Thus, the solution is:

3 dogs, 41 cats, and 56 mice.

This satisfies both the total number of animals (100) and the total cost ($100):

Cost of 3 dogs = 3 × 15 = $45,
Cost of 41 cats = 41 × 1 = $41,
Cost of 56 mice = 56 × 0.25 = $14,
Total cost = 45 + 41 + 14 = $100.

So, you need to buy 3 dogs, 41 cats, and 56 mice.

9

There is a general procedure or algorithm for solving linear Diophantine equations in two variables, but in this case it looks like trying to solve the problem that way is harder than the “trial and error but in a smart way” approach that people have taken here.

10

That doesn’t solve the non-negative constraint, though. There are an infinite number of solutions here given by 56D = 3M, but only one with a positive number of cats (and non-zero number of dogs/mice). So you still have to inspect the solutions by hand. And 56D = 3M is easy enough to solve by inspection (everyone should know the “if the number is a multiple of 3, then the sum of all digits is a multiple of 3” trick).

11

Right; and that’s part of the reason I thought that approach was harder than it was worth in this case.

12

I agree.

Dogs are easily 15 times better than cats.

13

…Aren’t you, yourself, a cat?

14

Beyond that, it’s still not an algebraic solution.

Not that there’s anything wrong with that (finding solutions is much better than not finding them), but it still stands that there generally aren’t algebraic solutions to Diophantine problems, elegant or not.

15

What do you mean by an “algebraic solution”? Consider an equation like 3x+2y=1, or better yet 123\,x+456\,y=7. If you specify that x and y must be integers, then no amount of algebra involving rational numbers or real numbers is going to help, because you need to use some properties of integers to find all the solutions (if any); we can call that (elementary) number theory. Things like Euclid’s Algorithm, depends on whether you want to call that algebra.

In general, by now it’s pretty famous that Hilbert’s Tenth Problem has been resolved, so there is no fancy algorithm that will work on any arbitrary polynomial. As opposed to over a field where you can do a bunch of algebra to solve a system of polynomial equations, like reduce it to one variable.

16

Pretty much taken directly from the OP - they were asking about a nifty or clever algebraic solution

17

I think I understand. But, then, the only algebra you need, or indeed can do, was already given in Post #2: just eliminate one of the variables (you cannot eliminate any more than that).

18

Maybe it is just worth noting, once we have done your algebra and expressed the numbers of the other animals in terms of the number of mice, in particular 56D=3M, there is still the bit where M and D are integers and at least one, so we know M is a non-zero multiple of 56 (and less than 100), which kind of narrows it down. (Not much “inspection” to do.)

Relaxing the constraint on the number of each animal being positive we would get an infinity of additional solutions like (C,D,M) = (100, 0, 0), (−18, 6, 112) and so on (M could be any multiple of 56)

19

I suppose you could simply substitute into an inequality:
56D = 3M
D + M < 100

D + (56/3)D < 100
59D < 300
D < 5.09

So that clearly rules out solutions of D=6, 9, etc.

ETA: And to keep it as entirely mental math:
59D < 300
50D < 300
D < 6

Same result, no calculator needed.

20

I believe he’s a fish.