124 views

Skip to first unread message

Sep 1, 1998, 3:00:00 AM9/1/98

to

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?

Sep 1, 1998, 3:00:00 AM9/1/98

to

> 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>

> Place a cat in the input bin of the first machine, press the button, and

> mouse. ***

Sep 1, 1998, 3:00:00 AM9/1/98

to

I'll never forget the time that Bob Harris <nit...@mindspring.com>

said:

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 ---

Sep 1, 1998, 3:00:00 AM9/1/98

to

nit...@mindspring.com wrote:

> > 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 "."

Sep 2, 1998, 3:00:00 AM9/2/98

to

Matthew Daly wrote:

> 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>

Sep 2, 1998, 3:00:00 AM9/2/98

to

In article <35ed4751...@news.kodak.com>,

>

> <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 mad veterinarian has created three animal transmogrifying machines.

> >

> >Place a cat in the input bin of the first machine, press the button, and

> >

> >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.

> >

> >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.> >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

Sep 2, 1998, 3:00:00 AM9/2/98

to

I'll never forget the time that Bob Harris <nit...@mindspring.com>

said:

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?

Sep 2, 1998, 3:00:00 AM9/2/98

to

Matthew Daly wrote: 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?

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.

Sep 2, 1998, 3:00:00 AM9/2/98

to

On Tue, 01 Sep 1998 15:19:55 -0400, Bob Harris

<nit...@mindspring.com> had this to say:

<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

Sep 2, 1998, 3:00:00 AM9/2/98

to

John Price wrote:

> 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*.

Sep 2, 1998, 3:00:00 AM9/2/98

to

nit...@mindspring.com wrote:

> 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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu