The mad veterinarian puzzle
Bob Harris
Place a cat in the input bin of the first machine, press the button, and
... whirrr ... bing! Open the output bins to find two dogs and five
mice.
The second machine can convert a dog into three cats and three mice, and
the third machine can convert a mouse into a cat and a dog. Each
machine can also operate in reverse (e.g. if you've got three cats and
three mice, you can convert them into a dog).
You have one cat.
1) Can you convert it into seven mice?
2) Can you convert it into a pack of dogs, with no mice or cats left
over?
Bob Harris
>
> Place a cat in the input bin of the first machine, press the button, and
> mouse. ***
Matthew Daly
said:
>A mad veterinarian has created three animal transmogrifying machines.
>
>Place a cat in the input bin of the first machine, press the button, and
>... whirrr ... bing! Open the output bins to find two dogs and five
>mice.
>
>The second machine can convert a dog into three cats and three mice, and
>the third machine can convert a mouse into a cat and a dog. Each
>machine can also operate in reverse (e.g. if you've got three cats and
>three mice, you can convert them into a dog).
>
>You have one cat.
>
>1) Can you convert it into seven mice?
>2) Can you convert it into a pack of dogs, with no mice or cats left
>over?
Interesting puzzle.
SPOILER
First, let's associate the process of the three machines with the
triplets (-1, 2, 5) (3, -1, 3) and (1, 1, -1) that gives the change in
cats, dogs, and mice respectively. (We'll allow for "negative" animals
here, which could represent animals that we started with at the
beginning of the process that were not replaced.) So, we can say that
if we use the first machine A times, the second machine B times, and the
third machine C times (where we understand negative values to mean that
we run the machine "in reverse"), the net change is (-A+3B+C, 2A-B+C,
5A+3B-C).
The first question asks if there are integral values for A, B, and C
such that the above triplet is (-1, 0, 7).
-A + 3B + C = -1
2A - B + C = 0
5A + 3B - C = 7
Multiply the middle equation by 3 and add it to each of the other
equations to get
5A + 4C = -1
11A + 2C = 7
Multiplying the second equation by -2 and adding it to the other yields
-17A = -15, so A must be a non-integer. Since there is no Diophantine
solution for this system of equations, there is no way to turn a cat
into seven mice. (Of course, it's easy to turn a cat into seven mice if
you allow the possibility of leftover animals, but I presume that's not
what we're supposed to be looking for.)
The second question asks if there are integral values for A, B, C, and N
such that the triplet is (-1, N, 0). In other words:
-A + 3B + C = -1
2A - B + C = N
5A + 3B - C = 0
Adding the first and third equations gives 4A + 6B = -1. No matter what
integral values we give to A and B, the expression on the left is even,
so there is no solution to this problem either.
ObPuzzle: You can turn a cat into just mice, though. Determine for a
given N if a cat can be turned into N mice.
-Matthew
--
Matthew Daly mwd...@pobox.com http://www.frontiernet.net/~mwdaly/
My opinions may have changed, but not the fact that I am right - Ashleigh Brilliant
The views expressed here are not necessarily those of my employer, of course.
--- Support the anti-Spam amendment! Join at http://www.cauce.org ---
Jamie Dreier
> > A mad veterinarian has created three animal transmogrifying machines.
> >
> > Place a cat in the input bin of the first machine, press the button, and
> > ... whirrr ... bing! Open the output bins to find *** four dogs and one
> > mouse. ***
> >
> > The second machine can convert a dog into three cats and three mice, and
> > the third machine can convert a mouse into a cat and a dog. Each
> > machine can also operate in reverse (e.g. if you've got three cats and
> > three mice, you can convert them into a dog).
> >
> > You have one cat.
> >
> > 1) Can you convert it into seven mice?
> > 2) Can you convert it into a pack of dogs, with no mice or cats left
> > over?
Well, applying Matthew's powerful method, I'll run the first machine,
getting four dogs and a mouse; then I'll run the second machine on a dog,
so I have three dogs, three cats, and four mice. Then I'll run the third
machine in reverse three times, finishing with seven mice.
It is impossible to finish with only dogs. Proof is easy, following
Matthew Daly's method.
-Jamie
--
SpamGard: For real return address replace "DOT" with "."
Bob Harris
> ObPuzzle: You can turn a cat into just mice, though. Determine for a
> given N if a cat can be turned into N mice.
SPOILER
A single cat can be turned into N mice iff N is of the form 34k+25, where k is a
non-negative integer.
Two move sequences suffice. First, you can turn the cat into 25 mice with the
following sequence:
1C -> 2D,5M (machine 1)
-> 6C,11M (machine 2, twice)
-> 4C,4D,21M (machine 1, twice)
-> 25M (machine 3, four times, in reverse)
Then 1 mouse can be turned into 35 mice with this sequence:
1M -> 1C,1D (machine 3)
-> 3D,5M (machine 1)
-> 9C,14M (machine 2, thrice)
-> 6C,6D,29M (machine 1, thrice)
-> 35M (machine 3, six times, in reverse)
The latter sequence can be used repeatedly to achieve 59 mice, 93 mice, and so on.
To prove that a single cat can not be turned into N mice if N is not of this form, you
can plug 34k+25 into the equations as described by Matthew Daly and see that there are
no integral solutions for k (or at least, this is what I claim).
ObPuzzle: What's the minimum number of cats necessary (by themselves) to create some
dogs (and nothing else)?
--
-- Bob Harris <nit...@atl.mindspring.com>
g...@w3.to
> >
> >Place a cat in the input bin of the first machine, press the button, and
> >mice.
> >
> >the third machine can convert a mouse into a cat and a dog. Each
> >machine can also operate in reverse (e.g. if you've got three cats and
> >three mice, you can convert them into a dog).
> >
> >You have one cat.
> >
> >1) Can you convert it into seven mice?
> >2) Can you convert it into a pack of dogs, with no mice or cats left
> >over?
>
>
> <snip>
>
>
> ObPuzzle: You can turn a cat into just mice, though. Determine for a
> given N if a cat can be turned into N mice.
>
>
A cat can be turned into 25 mice and a mouse into 35 mice, so values of N of
the form 25+34n (for natural n) are possible.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
Matthew Daly
said:
>ObPuzzle: What's the minimum number of cats necessary (by themselves) to create some
>dogs (and nothing else)?
SPOILER
We've already seen that we can't form all dogs with one cat. Starting
with 2 cats, we use machine 1 to form 1 cat, 2 dogs, and 5 mice. Then
we use machine 3 twice to form 3 cats, 4 dogs, and 3 mice, and then we
use machine 2 in reverse to form 5 dogs.
To show my work, we're starting with the following equations:
-A + 3B + C = -M
2A - B + C = N
5A + 3B - C = 0
where A, B, and C are integers and M and N are non-zero natural numbers.
We add the first and third equations to get 4A + 6B = -M. So M must be
a multiple of gcd(4, 6) = 2. Let's try setting M=2, A=1, and B=-1 to
see if this causes a solution to appear. (With more variables than
equations, it is likely that an infinite number of solutions exist, so
trying to pick one with small numbers will make our lives easier.)
Working these numbers into the third and second equations above, we see
that A=1, B=-1, C=2, M=2, and N=5 is a solution for the entire system of
equations. Therefore, using the first machine once, the second machine
backward once, and the third machine twice we can turn two cats into
five dogs. The actual process is shown above.
I guess I should say at some point in this thread that the numbers that
this equation turns out is not always attainable in practice. This is
because the theoretical solution allows you to have "negative animals"
that you can't have in the real world. For instance, if we had a
problem for turning all cats into all dogs that said that we should run
machine 2 5 times, it wouldn't work, because the last step would have to
be running machine 2 backwards. But the net result in reality is that
you would run machine 2 forwards 5 more times than you would run it
backwards.
ObPuzzle: Obviously, we can turn 5 dogs into 2 cats by reversing this
process. Is there a smaller number of dogs that can be turned into just
cats?
Bob Harris
> process. Is there a smaller number of dogs that can be turned into just
> cats?
Yep. One dog into fourteen cats with 8 operations.
Of course, we can always change the outcomes by feeding some of the mice to the cats
along the way.
John Price
<nit...@mindspring.com> had this to say:
>> A mad veterinarian has created three animal transmogrifying machines.
>>
>> Place a cat in the input bin of the first machine, press the button, and
>> ... whirrr ... bing! Open the output bins to find *** four dogs and one
>> mouse. ***
>>
>> The second machine can convert a dog into three cats and three mice, and
>> the third machine can convert a mouse into a cat and a dog. Each
>> machine can also operate in reverse (e.g. if you've got three cats and
>> three mice, you can convert them into a dog).
>>
>> You have one cat.
>>
>> 1) Can you convert it into seven mice?
>> 2) Can you convert it into a pack of dogs, with no mice or cats left
>> over?
>
SPOILER:
V
V
V
V
VV
V
V
V
V
V
V
V
V
V
V
V
V
V
V
First question:
1) throw the cat into the first machine.
2) throw one of the resulting dogs into the second machine.
3) throw a dog and a cat into the third machine and hit reverse.
4) repeat step 3 twice more.
5) ta-da!
Second question:
Unless I miss my guess, this is impossible ... the final step must be
throwing 3 cats and 3 mice into machine 2. But we can never have an
equal number of cats and mice, since machines 1 and 3 convert 1c-->1m
or 1m-->1c, always leaving us with an odd difference in the number of
mice and cats. (excuse the informal logic) And, well, machine 2 just
makes an equal number of each, so that doesn't help. Am I missing
something?
Cheers,
John
Bob Harris
> Second question:
>
> Unless I miss my guess, this is impossible ... Am I missing something?
Nope. The second part was supposed to be impossible. The puzzle is in
proving *why*.
Jamie Dreier
> Nope. The second part was supposed to be impossible. The puzzle is in
> proving *why*.
Well, I could post a proof, but really, Matthew Daly's proof of the
earlier question, the one that had the first machine produce five mice and
two dogs, that proof showed the method. The rest is just plodding through
it again with different numbers.