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

**URL:** <https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269>\
**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:** 4\
**Page:** 2

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [October 28, 2024, 1:08am UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/21 "2024-10-28T01:08:37Z")

</div>

You may be mixing up the adorable _gato pescador_  
[![](https://upload.wikimedia.org/wikipedia/commons/f/f7/Prionailurus_viverrinus_01.jpg) ](https://upload.wikimedia.org/wikipedia/commons/f/f7/Prionailurus_viverrinus_01.jpg)  
with el “pez gato”  
[![](http://assets.tvu.cl/2017/08/Pez-gato.jpg) ](http://assets.tvu.cl/2017/08/Pez-gato.jpg)

---

<div class="post-metadata">

**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 28, 2024, 8:52pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/22 "2024-10-28T20:52:36Z")

</div>

> [@DPRK](#):
>
> What do you mean by an “algebraic solution”? Consider an equation like 3x+2y=13x+2y=13x+2y=1, or better yet 123,x+456,y=7123x+456y=7123,x+456,y=7. If you specify that xxx and yyy 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.

Okay, let’s look at those equations. The second one obviously has no solutions since 3 divides the left hand side and not the right. Don’t need to know much for that one. As for 3x+2y=1, that is the same as x=\frac{1-2y}3 so that in any solution, it must be the case that 3|1-2y (the vertical line means divides), and the only way that can happen is that y=3k+1 for an integer k. How do I know that? Divide y by 3 and call the remainder the quotient k and the remainder r. When r=0 or r=2, it is easy to see that 1-2y is not divisible by 3 and when r=1 it is. Then y=3k+1, we see that 1-2y=-3-6k and then x=\frac{1-2k}3=-1-2k and that gives all the solutions. Had the second equation been 123x+457y=6, the same methods would have worked, provided you knew the prime divisors of the coefficients, although more tedious.

---

<div class="post-metadata">

**Author:** ![Pleonast](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pleonast/32/1183_2.png) [@Pleonast](https://boards.straightdope.com/u/Pleonast)\
**Post date:** [October 28, 2024, 9:53pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/23 "2024-10-28T21:53:25Z")

</div>

Without looking at any other answers:

**Set up**  
Number of dogs, cats, mice, which are all integers:  
(1) 1 \<= d \< 100  
(2) 1 \<= c \< 100  
(3) 1 \<= m \< 100

Limit on number:  
(4) 100 = d + c + m

Limit on cost:  
(5) 100 = 15d + c + \frac{1}{4}m

**Solution**  
Eq(5) multiplied by 4:  
(6) 400 = 60d + 4c +m

Eq(6) minus Eq(4):  
(7) 300 = 59d + 3c

Eq(7) solved for c:  
(8) c = 100 - \frac{59}{3}d

Eq(3) solved for m:  
(9) m = 100 - d - c

Eq(9) with Eq(8) substituted in:  
(10) m = 100 - d - (100 - \frac{59}{3}d) = \frac{56}{3}d

From Eq(8), Eq(10), d is an integer:  
(11) d = 3n for some integer n.

Eq(10) with Eq(11) substituted in:  
(12) m = 56n

Rel(3) with Eq(12) substituted in:  
(13) 1 \<= 56n \< 100

By inspection, only one integer satisfies Rel(13):  
(14) n = 1

Eq(12) with Eq(14) substituted in:  
(15) m = 56(1) = 56

Eq(11) with Eq(14) substituted in:  
(16) d = 3(1) = 3

Eq(8) with Eq(16) substituted in:  
(17) c = 100 - \frac{59}{3}(3) = 41

**Therefore, 3 dogs, 41 cats, and 56 mice.**

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [October 28, 2024, 11:14pm UTC](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269/24 "2024-10-28T23:14:55Z")

</div>

Working modulo 3, if 1-2y is divisible by 3, then y=3k+2 [not 1]; I guess we can call that algebra in the field \mathbb{Z}/3\mathbb{Z}. We get the set of solutions (x,y) = (-2k-1,3k+2).

If the numbers are big— let’s take 123x+457y=6, the same methods work— in finding the modular multiplicative inverse we might want to use Euclid’s algorithm, which gives 123\cdot(-26)+457\cdot7=1. So, now, multiplying through by 6, we get (x,y)=(457k-156,-123k+42).

[Previous page](https://boards.straightdope.com/t/math-experts-find-an-elegant-solution-for-this-car-talk-puzzler/1009269.md?page=1)