## Cat and mouse v.2

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

lexolf
Posts: 2
Joined: Sun Sep 18, 2016 6:36 am UTC

### Cat and mouse v.2

So, this seems like a follow up on quite an old topic here:
http://forums.xkcd.com/viewtopic.php?f=3&t=62767

My friend told our group one:
There are 5 holes in which the mouse can hide. They are arranged in line 1-2-3-4-5. 1 and 5 holes are not connected, while others are.
The cat doesn't know where mouse is and can't hear it or in any way (except logical reasoning) know where the mouse is.
The cat can put its paw into any hole, but only one at a time.
Each one attempt of the cat leads to the mouse's one move.
The mouse randomly moves in any direction (left or right), and the mouse moves simultaneously with cat's paw insertion. So, it means that if the mouse is in the hole #3 and the cat puts the paw in it, the mouse escapes to #2 or #4. Or, if the mouse is in #1 and the cat puts its paw in #2, the mouse has no way but run straight into cat's paw.

So, the question our friend gave us:
What is the minimal number of paw insertions needed to guarantee that the cat catches the mouse?
And what is this sequence?

However, after quite a large number of attempts to solve it, it seems like it has no solution. But still, I don't know how to prove it properly.

Maybe you'll give it a try?

DaBigCheez
Posts: 829
Joined: Tue Jan 04, 2011 8:03 am UTC

### Re: Cat and mouse v.2

If I'm reading this correctly, it looks like it's identical to the original cat and mouse problem that you linked, with the exceptions that:

1) the movement of the mouse occurs simultaneously with/"before" the cat's paw, so the cat has to place its paw in the mouse's destination rather than its current position.
2) the movement of the mouse is random, rather than willful.

Is that correct?

Spoiler:
If so, it would seem that the solution's identical to that of the original problem. The "simultaneity" really doesn't change anything, it just puts things "one turn behind" - and the randomness doesn't really change anything, since the worst-case scenario would be the same as a "malicious" mouse that will never run straight into our paw if it is possible to avoid it.

In that case, the solution, as in the original, is a sequence of 6 moves: 2, 3, 4, 2, 3, 4. The initial conditions for when you get the hit are slightly different, though. If the mouse starts on an odd-numbered space, the first 2-3-4 sweep will catch it; if it starts on an even-numbered space, the second one will. (This can be easily verified by charting out the possible spaces the mouse can end in after each move, and showing that they intersect with the given sequence at at least one point.)

Effectively, all you're doing by the "simultaneity" clause is changing the mouse's location by one space on the first move, and since the optimal solution doesn't (and can't) depend on its starting space, nothing changes.
existential_elevator wrote:It's like a jigsaw puzzle of Hitler pissing on Mother Theresa. No individual piece is offensive, but together...

If you think hot women have it easy because everyone wants to have sex at them, you're both wrong and also the reason you're wrong.

lexolf
Posts: 2
Joined: Sun Sep 18, 2016 6:36 am UTC

### Re: Cat and mouse v.2

DaBigCheez, yes, that is correct.

And now I feel dumb because I saw that solution in previous topic, tried it and it didn't work. Somehow.
When I tried it again now, I finally can't find a way the mouse escapes.

Thank you.

Maybe I just need more sleep

PS: does it mean the topic should be deleted since it's the same puzzle?