# Math experts: Find an elegant solution for this Car Talk puzzler **URL:** \ **Category:** In My Humble Opinion\ **Created:** [October 26, 2024, 8:33pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269 "2024-10-26T20:33:58Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![commasense](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/commasense/32/3017_2.png) [@commasense](https://boards.straightdope.com/u/commasense)\ **Post date:** [October 26, 2024, 8:33pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/1 "2024-10-26T20:33:58Z")
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.](https://www.cartalk.com/radio/puzzler/cats-and-dogs-and-mice-oh-my) Surely our resident math whizzes can find a better method, right? Answer: 3 dogs, 41 cats, 56 mice. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [October 26, 2024, 8:49pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/2 "2024-10-26T20:49:01Z")
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. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [October 26, 2024, 8:51pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/3 "2024-10-26T20:51:41Z")
There’s not going to be an “elegant” solution here, as they note. This is an example of what’s called a [Diophantine problem](https://en.wikipedia.org/wiki/Diophantine_equation). 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. ---
**Author:** ![Dr.Winston\_OBoogie](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.winston_oboogie/32/2945_2.png) [@Dr.Winston\_OBoogie](https://boards.straightdope.com/u/Dr.Winston_OBoogie)\ **Post date:** [October 26, 2024, 8:54pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/4 "2024-10-26T20:54:44Z")
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 ---
**Author:** ![commasense](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/commasense/32/3017_2.png) [@commasense](https://boards.straightdope.com/u/commasense)\ **Post date:** [October 26, 2024, 9:07pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/5 "2024-10-26T21:07:41Z")
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. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [October 26, 2024, 9:45pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/6 "2024-10-26T21:45:05Z")
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. ---
**Author:** ![commasense](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/commasense/32/3017_2.png) [@commasense](https://boards.straightdope.com/u/commasense)\ **Post date:** [October 27, 2024, 12:29am UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/7 "2024-10-27T00:29:35Z")
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. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [October 27, 2024, 5:18am UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/8 "2024-10-27T05:18:40Z")
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. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [October 27, 2024, 3:33pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/9 "2024-10-27T15:33:39Z")
> [@Great\_Antibob](#): > > This is an example of what’s called a [Diophantine problem](https://en.wikipedia.org/wiki/Diophantine_equation). 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. 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. > **[How to Solve a Linear Diophantine Equation (with Pictures)](https://www.wikihow.com/Solve-a-Linear-Diophantine-Equation)** > > Solving a linear Diophantine equation means that you need to find solutions for the variables x and y that are integers only. Finding integral solutions is more difficult than a standard solution and requires an ordered pattern of steps.... ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [October 27, 2024, 6:54pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/10 "2024-10-27T18:54:38Z")
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). ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [October 27, 2024, 6:58pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/11 "2024-10-27T18:58:20Z")
> [@Dr.Strangelove](#): > > That doesn’t solve the non-negative constraint, though. Right; and that’s part of the reason I thought that approach was harder than it was worth in this case. ---
**Author:** ![Gatopescado](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/gatopescado/32/5711_2.png) [@Gatopescado](https://boards.straightdope.com/u/Gatopescado)\ **Post date:** [October 27, 2024, 8:46pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/12 "2024-10-27T20:46:51Z")
I agree. Dogs are easily 15 times better than cats. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 27, 2024, 8:55pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/13 "2024-10-27T20:55:16Z")
…Aren’t you, yourself, a cat? ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [October 27, 2024, 9:10pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/14 "2024-10-27T21:10:52Z")
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. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 27, 2024, 10:06pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/15 "2024-10-27T22:06:05Z")
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. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [October 27, 2024, 11:21pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/16 "2024-10-27T23:21:44Z")
Pretty much taken directly from the OP - they were asking about a nifty or clever algebraic solution ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 27, 2024, 11:32pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/17 "2024-10-27T23:32:17Z")
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). ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 27, 2024, 11:55pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/18 "2024-10-27T23:55:28Z")
> [@Dr.Strangelove](#): > > 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). 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) ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [October 28, 2024, 12:05am UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/19 "2024-10-28T00:05:20Z")
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. ---
**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\ **Post date:** [October 28, 2024, 1:01am UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/20 "2024-10-28T01:01:50Z")
> [@Chronos](#): > > …Aren’t you, yourself, a cat? I believe he’s a fish. [Next page](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269.md?page=2)