Cat and mouse

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Лом
Posts: 13
Joined: Fri Jul 23, 2010 1:02 pm UTC

Cat and mouse

Postby Лом » Tue Jul 27, 2010 6:59 am UTC

There are 5 holes where mouse can hide, arranged in a line:
(1) - (2) - (3) - (4) - (5)
Mouse can hide in any hole. Two adjancent holes are connected, so mouse can go from hole 1 to 2, from 2 to 1 or 3 ... from 4 to 3 or 5, and from 5 to 4.

Cat is sitting in front of the holes. He does not know in which hole mouse is hiding.

He can do the following: check any hole with paw, if there is mouse inside he can catch it, if not he remove his paw from hole.
After each cat attemp mouse must switch hole, because she is very afraid. Mouse cannot remain in the same hole she must move to adjancent one.
Than the cat can check another hole and the process repeats.

Question: Is cat able to catch the mouse?

P.S. Sorry if this puzzle was already published, I didn't found it.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cat and mouse

Postby jaap » Tue Jul 27, 2010 8:26 am UTC

This is a very nice puzzle I hadn't seen before.
My answer:
Spoiler:
The cat can try 2,3,4,2,3,4.
If the mouse starts of in on even numbered hole, then the first 2,3,4 pass will catch it. If it is in an odd numbered hole then it will not be caught by the first pass, but it will end up in an even numbered hole so that the second pass will catch it.

Proof that 2,3,4 will catch the mouse if it starts on an even numbered hole:

If mouse is in 2, it is caught immediately.
If it starts in 4, then in the second step the mouse must be in 3 or 5. If in 3, it is caught.
If it is not caught in the second step, it must have been in 5, so it will move to 4and be caught in the third step.


My first solution was 1,2,3,4,5,1,2,3,4,5. My second was 1,2,3,4,X,1,2,3,4 where X is any move. Only then did I simplify it to the above.

User avatar
Lothar
Posts: 63
Joined: Sat Dec 23, 2006 11:37 am UTC
Location: Berlin, Germany
Contact:

Re: Cat and mouse

Postby Lothar » Tue Jul 27, 2010 8:35 am UTC

Indeed, quite a fun one!
Spoiler:
The cat can also try 2, 2, 4, 4, 4, 2. If the mouse is in 1 or 2, the cat will catch it in the first two tries. After this, the mouse is in 3, 4, or 5. If it is in 4 or 5, the next two 4's will catch it. So the mouse must have been on 3 after the first two tries to survive this long. In the second two tries, the mouse can't pass through 4, so it must be on 1 or 3. After another try at 4, the mouse is either caught or on 2, so try 2.

I wonder if 6 moves is the best the cat can do. Anyone have a proof or a counterexample?
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.

If you're not part of the solution, you're part of the precipitate.

1+1=3 for large values of 1.

bobleboffon3
Posts: 38
Joined: Fri Jul 16, 2010 7:35 am UTC

Re: Cat and mouse

Postby bobleboffon3 » Tue Jul 27, 2010 8:47 am UTC

Spoiler:
jaap's answer looks good.

I think any answer with repetitive sequence will work as long as the sequence will mix the odd/even attempt. i.e. you try "2" on an even try, then on a odd try.

It's easy to proove the 2-3-4 method works.

Let's call the moves 1st, 2nd, and 3rd.
(first move always being 2, second move always being 3, and third move always being 4)

Mouse can't be in the following locations :
Hole 2 first move.
Hole 3 second move.
Hole 4 third move.

From this, we can find out that the mouse can't be in :
Hole 1 third move
Hole 5 second move
(If the mouse is in hole 1 third move, it'll be in hole 2 first move, and if it's on hole 5 second move, it'll be in hole 4 third move)

From this we can find out that the mouse can't be in :
Hole 4 first move ( if the mouse is in hole 4 first move, it'll be in hole 3 or hole 5 for second move, and as previously proved, those holes are both forbidden )

From this we can find out that the mouse can't be in :
Hole 5 third move
Hole 3 third move
(If the mouse is in hole 5 or 3 during the third move, it'll be in hole 2 or 4 during the first move, and both these holes are forbidden )

From this we can find out that the mouse can't be in :
Hole 4 second move
Hole 2 second move
(If the mouse is in hole 2 or 4 during the second move, it'll be in hole 1 or 3 during the third move, and both these holes are forbidden)

From this we can find out that the mouse can't be in :
Hole 5 first move
Hole 3 first move
Hole 1 first move
(if the mouse is in hole 1, 3 or 5 during the first move, it'll be in hole 2 or 4 during the second move, and both these holes are forbidden)

And from this point, we can say the mouse can't do anything all at, because we just proved it's can't be in any of the 5 holes for the first move.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cat and mouse

Postby jaap » Tue Jul 27, 2010 9:16 am UTC

Lothar, Your solution doesn't work:
Spoiler:
Lothar wrote:The cat can also try 2, 2, 4, 4, 4, 2.
The mouse could be in holes 4,3,2,1,2,1 when those moves are made, or 5,4,3,2,3,4.
Lothar wrote:If the mouse is in 1 or 2, the cat will catch it in the first two tries. After this, the mouse is in 3, 4, or 5.
After this the mouse will do another move and end up in 2,3,4 or 5 when the cat does its next grab.

Лом
Posts: 13
Joined: Fri Jul 23, 2010 1:02 pm UTC

Re: Cat and mouse

Postby Лом » Tue Jul 27, 2010 9:50 am UTC

Yes, you got the right answer :)
I wondering, what if there is N holes. Is cat still able to catch mouse?

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cat and mouse

Postby jaap » Tue Jul 27, 2010 9:58 am UTC

Лом wrote:Yes, you got the right answer :)
I wondering, what if there is N holes. Is cat still able to catch mouse?

My solution generalises:
Spoiler:
If N is odd, do 2,3,4,..,N-1 twice.
If N is even, do 2,3,4,..,N-1, any other move, and then 2,3,4,..,N-1 again.

If the mouse starts on an even number, the first pass is guaranteed to get it as the mouse cannot pass through from the right to the left of the cat's paw. The second pass gets the mouse if it started on an odd number.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Cat and mouse

Postby aleph_one » Tue Jul 27, 2010 4:16 pm UTC

I got a slightly cleaner version of jaap's answer: If there are N holes (with N at least 3), the cat can catch the mouse in 2(N-2) rounds by doing
Spoiler:
2, 3, ..., N-1 then N-1, ..., 3, 2

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Cat and mouse

Postby t1mm01994 » Tue Jul 27, 2010 5:00 pm UTC

Just to check
Spoiler:
for 3
2,2 does the trick.
for 4
2,3,3,2
Does the trick.
2,3,4,4,3,2
Does the trick.
I believe him ^

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Cat and mouse

Postby Torn Apart By Dingos » Thu Jul 29, 2010 4:03 am UTC

I read another wording of this puzzle on a thread on mathoverflow and got exactly the same solution as aleph_one. The wording of the puzzle in that thread seems to imply that 2(N-2) is the best we can do. How could we prove this?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Cat and mouse

Postby jestingrabbit » Thu Jul 29, 2010 5:53 am UTC

I think that you'd have to begin by proving that some moves are ineffective. Call a mouse an O-mouse if begins in an odd hole, an E-mouse otherwise. If in my first move I inspect an odd hole, and then another odd hole, then when I begin my third move the mouse may be on any odd hole, so my first move is wasted. From a generalisation of that I would go on to prove that you had to deal with one of the possibilities ie of an O-mouse or an E-mouse, before you deal with the other possibility.

From there you'd talk about the problems with making an initial move in the middle of the holes: the possible mice can make all the correct parity holes possible for your next move so that your first was pointless. So your first move has to be at the first possible hole for the mice you are dealing with, from one end or the other. Generalising that result, you'd demonstrate that you have to keep hacking away at the same end of the list of possible parity-correct holes.

I think we're in striking distance from there.

So, I would probably wave my hands around wildly. That's how I'd prove it.

Edit: Fixed some errors.

Edit: That first paragraph can be a lot simpler. Just something about "there are two cases you need to deal with, and action wrt one is not helpful wrt the other."
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

campboy
Posts: 52
Joined: Wed Jun 18, 2008 1:54 am UTC

Re: Cat and mouse

Postby campboy » Thu Jul 29, 2010 11:23 pm UTC

post deleted
Last edited by campboy on Tue Jun 28, 2011 1:26 pm UTC, edited 1 time in total.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Cat and mouse

Postby ++$_ » Sat Jul 31, 2010 4:50 am UTC

Here's a follow-up:

Another mouse, seeing the fate of the last one, builds two extra rows of mouse holes. The holes are organized like this:

Code: Select all

(A1)(A2)(A3)(A4)(A5)
(B1)(B2)(B3)(B4)(B5)
(C1)(C2)(C3)(C4)(C5)
The mouse may only move vertically or horizontally (not diagonally) between holes.

When the cat sees this, she is disappointed at first, but soon realizes that she has two front paws for a reason. She begins to make jabs into the holes with both paws, catching the mouse if it is in either of the two holes selected. As usual, the mouse must switch to an adjacent hole after every attempt. Can the cat be sure that she will catch the mouse?

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cat and mouse

Postby jaap » Mon Aug 02, 2010 9:12 am UTC

++$_ wrote:Another mouse, seeing the fate of the last one, builds two extra rows of mouse holes. The holes are organized like this:

Code: Select all

(A1)(A2)(A3)(A4)(A5)
(B1)(B2)(B3)(B4)(B5)
(C1)(C2)(C3)(C4)(C5)
The mouse may only move vertically or horizontally (not diagonally) between holes.

When the cat sees this, she is disappointed at first, but soon realizes that she has two front paws for a reason. She begins to make jabs into the holes with both paws, catching the mouse if it is in either of the two holes selected. As usual, the mouse must switch to an adjacent hole after every attempt. Can the cat be sure that she will catch the mouse?


Yes, this is possible.
Spoiler:
If you give the holes a checkerboard colouring, the mouse will have to move from a white hole to a black one, and vice versa between each of the cat's attempts. Below is a sequence of 11 moves that catches the mouse if it starts in one of the colours, the holes named A2,A4,B1,B3,B5,C2,C4.
An x denotes a possible location of the mouse, an O denotes a hole that the cat puts his paw into (which is also one of the possible locations of the mouse).
By doing this sequence twice, the mouse will be caught whichever colour hole it started on.

Code: Select all

. x . x .
O . x . x
. O . x .

O . x . x
. O . x .
. . x . x

. O . x .
. . x . x
. O . x .

. . x . x
. O . x .
. . O . x

. O . x .
. . O . x
. . . x .

. . O . x
. . . x .
. . O . x

. . . x .
. . O . x
. . . O .

. . O . x
. . . O .
. . . . x

. . . O .
. . . . x
. . . O .

. . . . x
. . . O .
. . . . O

. . . O .
. . . . O
. . . . .

drkfalco
Posts: 12
Joined: Wed Aug 04, 2010 2:15 am UTC

Re: Cat and mouse

Postby drkfalco » Wed Aug 04, 2010 6:22 am UTC

The easiest way is 2,2,3,3,4,4... you catch it with those sequence,try it =)...

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Cat and mouse

Postby phlip » Wed Aug 04, 2010 6:40 am UTC

drkfalco wrote:The easiest way is 2,2,3,3,4,4... you catch it with those sequence,try it =)...

Not if the mouse goes 4,3,2,1,2,1.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

akahelio
Posts: 4
Joined: Sat Aug 07, 2010 1:31 am UTC

'c' pgm solves Cat and mouse

Postby akahelio » Sat Aug 07, 2010 2:06 am UTC

Hope this is all correct. I used ABCDE rather than 12345 for the holes.

Spoiler:
A <-- 1 solution for 1 mousehole

AA <-- 2 solutions for 2 mouseholes
BB

BB <-- 1 solution for 3 mouseholes

BCCB <-- 2 solutions for 4 mouseholes
CBBC

DCBDCB <-- 4 solutions for 5 mouseholes
BCDDCB
DCBBCD
BCDBCD

BCDEEDCB <-- 2 solutions for 6 mouseholes
EDCBBCDE

FEDCBFEDCB <-- 4 solutions for 7 mouseholes
BCDEFFEDCB
FEDCBBCDEF
BCDEFBCDEF

From the symmetry of the solutions above, apparently (?) for n mouseholes, one GENERAL SOLUTION to the puzzle would be:
n-1, n-2, ... 2,2, ... n-2, n-1
Examples of a general solution:
3 holes: 2,2 or BB (where 2=B, 3=C, 4=D 5=E 6=F etc.)
4 holes: 3,2,2,3 or CBBC
5 holes: 4,3,2,2,3,4 or DCBBCD
6 holes: 5,4,3,2,2,3,4,5 or EDCBBCDE
7 holes: 6,5,4,3,2,2,3,4,5,6 or FEDCBBCDEF

Here's how the pgm derives the DCBDCB solution for 5 mouseholes, by letting the mouse start in each possible mousehole, and make all the possible moves from there:

ABABAB <== The MOUSE gets caught in the last hole shown
DCBDCB

ABABC <== mouse caught
DCBDCB

ABCBAB <== mouse caught
DCBDCB

ABCBC <== mouse caught
DCBDCB

ABCD <== mouse caught
DCBDCB

BAB <== mouse caught
DCBDCB

BC <== mouse caught
DCBDCB

CBABAB <== mouse caught
DCBDCB

CBABC <== mouse caught
DCBDCB

CBCBAB <== mouse caught
DCBDCB

CBCBC <== mouse caught
DCBDCB

CBCD <== mouse caught
DCBDCB

CDCBAB <== mouse caught
DCBDCB

CDCBC <== mouse caught
DCBDCB

CDCD <== mouse caught
DCBDCB

CDED <== mouse caught
DCBDCB

D <== mouse caught
DCBDCB

EDCBAB <== mouse caught
DCBDCB

EDCBC <== mouse caught
DCBDCB

EDCD <== mouse caught
DCBDCB

EDED <== mouse caught
DCBDCB

The mouse tried everything, but there is NO WAY OUT
*** The cat wins; puzzle is SOLVED!

User avatar
Tualha
Posts: 69
Joined: Wed Dec 12, 2007 12:18 pm UTC

Re: Cat and mouse

Postby Tualha » Wed Aug 11, 2010 9:38 am UTC

This is not an elegant solution, but it's simple. Question was not "how does cat catch mouse in fewest moves" but "is cat able to catch mouse". Answer is yes. Cat tries a random hole each time. Eventually mouse's luck runs out.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Cat and mouse

Postby jestingrabbit » Wed Aug 11, 2010 11:48 am UTC

That guarantees that the mouse will almost surely catch the mouse. Compared to being sure that you will catch the mouse, that's a pretty small consolation.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Cat and mouse

Postby mike-l » Wed Aug 11, 2010 1:47 pm UTC

Tualha wrote:This is not an elegant solution, but it's simple. Question was not "how does cat catch mouse in fewest moves" but "is cat able to catch mouse". Answer is yes. Cat tries a random hole each time. Eventually mouse's luck runs out.


You'll catch him with probability 1, but that doesn't guarantee you'll catch him.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
garak1a
Posts: 23
Joined: Mon Apr 20, 2009 5:21 pm UTC

Re: Cat and mouse

Postby garak1a » Tue Sep 14, 2010 7:16 pm UTC

I liken this solution to a boy's answer to a simply math problem: Three crows are sitting on a power line. A hunter shoots one, how many are left? The boy replies zero, because the other two were scared off by the noise of the gun and the sudden death of their companion.


Putting yourself in the position of the mouse: If I were the mouse, there's no way I'd ever go into the hole that the cat just attacked. No way. It risks of being attacked again, per my rodent logic.

So the simplest solution would be for the cat to simply try 1-2-3-4-5. If the mouse was in 3, 4, or 5, it will undoubtedly eventually move into the path of the paw. If it was in 2, then it will slowly move to 5, until dying of a logical fallacy (forced to move out of #5, but refuses to move to #4, which was just attacked.)
10 dollar solo
Worth every dime
My path it is steep
But my god Joss is cheap
And doesn't mind wasting your time

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Cat and mouse

Postby jestingrabbit » Tue Sep 14, 2010 9:51 pm UTC

The point of the logic puzzles forum isn't to bring in real world factors, its to examine the logic of a situation as presented and answer them on their own terms.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Cat and mouse

Postby mike-l » Wed Sep 15, 2010 1:35 pm UTC

jestingrabbit wrote:The point of the logic puzzles forum isn't to bring in real world factors, its to examine the logic of a situation as presented and answer them on their own terms.


While I agree... I like death by logical fallacy. I'd like to put that on my tombstone: "Here lies mike-l, died of a logical fallacy."
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

ericgrau
Posts: 92
Joined: Sat Dec 13, 2008 7:14 pm UTC

Re: Cat and mouse

Postby ericgrau » Fri Oct 01, 2010 3:34 am UTC

Spoiler:
2, 2: mouse caught or did not start in space 1 nor move to space 1 on first move. Mouse must now move from 3, 4, or 5 to 2, 3, 4 or 5.
3: Mouse caught or moved to 2, 4 or 5. Mouse must now move from there to 1,3, 4 or 5. Can't reach 2 because wasn't in 1 or 3.
4: Mouse caught or moved to 1,3 or 5. Must now move from there to 2 or 4.
4: Mouse caught or was in 2. Must now move to 1 or 3.
3: Mouse caught or was in 1. Must now move to 2.
2: Mouse caught. For bonus points, cat also played first 7 notes of Ode to Joy.


EDIT: Ok, so others did it and a step faster. I wanted to give it a try before reading someone else's solution.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Cat and mouse

Postby snowyowl » Sat Oct 02, 2010 10:51 pm UTC

ericgrau wrote:
Spoiler:
For bonus points, cat also played first 7 notes of Ode to Joy.


I think I can safely say that this is the best solution.
The preceding comment is an automated response.

akahelio
Posts: 4
Joined: Sat Aug 07, 2010 1:31 am UTC

your 7 pokes is not best solution ...

Postby akahelio » Tue Oct 12, 2010 3:57 pm UTC

The puzzle can be solved in 6 pokes in 4 different ways (see 'c' pgm solves Cat and mouse)

DCBDCB <-- 4 solutions for 5 mouseholes
BCDDCB
DCBBCD
BCDBCD

your solution, with the extra first poke, is closest to
BCDDCB ie 234432

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Cat and mouse

Postby rmsgrey » Tue Dec 04, 2012 3:33 pm UTC

snowyowl wrote:
ericgrau wrote:
Spoiler:
For bonus points, cat also played first 7 notes of Ode to Joy.


I think I can safely say that this is the best solution.


Particularly managing 7 notes with only 6 moves...

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

Re: Cat and mouse

Postby Elmach » Wed Dec 05, 2012 7:18 am UTC

So by now we all know that the best solution is 6 paws, and a few of them are given above.

What if the five holes are arranged in a circle? Mouse in A can go to B or E, B to A or C, C to B or D, D to C or E, E to D or A. Mouse has to change holes each time. Is there a strategy for the cat to catch the mouse in a finite number of moves? (Probability 1 is not enough, must be a sure thing, not almost sure)

Spoiler:
I think not, the cat can never narrow the mouse's position down to one hole. If the cat knows that the mouse is in either position A or C, and hits A and fails, the mouse is now in either B or D. Rotate left, repeat.

User avatar
patzer
Posts: 431
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

Re: Cat and mouse

Postby patzer » Wed Dec 05, 2012 8:46 am UTC

Possible answer to Elmach's puzzle
Spoiler:
I don't think it's possible; without edges the cat can't box the mouse in and also there is no odd/even parity trick. The 4-hole version looks more interesting as there may be a parity trick but I can't see a solution yet.
If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family Anatidae on our hands. –Douglas Adams

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cat and mouse

Postby jaap » Wed Dec 05, 2012 9:18 am UTC

Elmach wrote:So by now we all know that the best solution is 6 paws, and a few of them are given above.

What if the five holes are arranged in a circle? Mouse in A can go to B or E, B to A or C, C to B or D, D to C or E, E to D or A. Mouse has to change holes each time. Is there a strategy for the cat to catch the mouse in a finite number of moves? (Probability 1 is not enough, must be a sure thing, not almost sure)

Spoiler:
I think not, the cat can never narrow the mouse's position down to one hole. If the cat knows that the mouse is in either position A or C, and hits A and fails, the mouse is now in either B or D. Rotate left, repeat.

Spoiler:
Indeed, it is impossible. Whatever move the cat does, after the mouse moves it can be in any of the holes. Some are more likely than others, but none have been eliminated. The same goes for any subsequent moves - all holes have a non-zero probability of containing the mouse.



If the cat is allowed to use two paws, as mentioned in one of the variants above, then it is easy because one paw can be used as an edge to split the ring into a row, with the other paw using one of the solutions to the original puzzle. With a ring of 6 holes it is therefore possible for the cat to get the mouse in 6 double-paw moves (e.g. one paw repeatedly going in hole 6, with the other paw doing 2,3,4,2,3,4). Surely this can be done in fewer double-paw moves?
Spoiler:
For even n it can be done in n-2 double-paw moves, for odd n in n-1, but I'm not sure those are optimal.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 42 guests