Can a cat ever catch a mouse in a circular maze?

[Bartholomew]

I recommend the 2nd teaser in Cat and Mouse (I posted a new teaser in that thread) before you try this one. This is mad difficult (unless you have some insight which I didn't), and I've flip-flopped more than once before coming to what I believe is the right answer. But it's still just a reasoning puzzle; you don't need advanced math.

Can 1 cat (a point) catch 1 mouse (a point) if they move at the same speed within a circle and start out so that the cat has not already caught the mouse? (to catch the mouse, he must do it in a finite amount of time)

 

[DaveC426913]

Answer:

Yes. Since their speeds are the same, the only time the mouse can maintain the separation is when it is moving directly away from the cat. Every time the mouse makes a turn, the cat closes the distance slightly. Being constrained forces the mouse to alter its path.

Not so difficult.

 

[Bartholomew]

Nope, that's not enough of an answer. The cat can get closer to the mouse but you have not demonstrated he can ever catch it. For example, say that the mouse runs around the circumference of the circle and the cat's plan is to always keep between the mouse and the center of the circle. The cat does not have to travel as far as the mouse does (since the radius of his circle is smaller), so he can use his extra speed to approach the mouse as they turn. But as he gets closer and closer to the mouse, the cat has to travel almost as far as the mouse does just to keep the same rotational speed. When the cat is separated from the mouse by only an infinitesimal distance, the cat must go as fast as the mouse does just to keep up the rotational speed and thus he has no speed left over to approach the mouse. So with this strategy although the cat may get continually closer to the mouse, he may not catch it.

(P.S. The cat does have more promising strategies than that)

 

[NateTG]

Can 1 cat (a point) catch 1 mouse (a point) if they move at the same speed within a circle and start out so that the cat has not already caught the mouse? (to catch the mouse, he must do it in a finite amount of time)

Let's say that the cat and mouse start separated by a distance $d$ and the cat's strategy is simply to go towards the mouse's current location. Since the cat is always going to be moving towards the mouse at least as fast as the mouse is moving, it will never loose distance. Clearly, if the mouse must run in a direction that is generally away from the cat.

Now, whenever the mouse turns an angle $\theta$ in time $t$, the cat gains approximately:
$$st(1-\sqrt{2-2\cos\theta})$$
on the mouse, where $\theta$ is the angle that the mouse turns though and $t$ is the time increment. Because the mouse is trapped in the circle, it must travel through an angle of $2\pi$ for every $2\pi r$ distance it moves.

Now, from the equation above it's clear that the mouse wants to make small turns rather than sharp ones so let's take a look at gradual changes:
Let's say that the mouse makes $$n$$ turns of angle [tex]\frac{\theta}{n}[/itex] over time $$t$$<br /> then the cat gains<br /> $$\lim_{n\rightarrow\infty} \frac{1}{n} \times n \times (1 - \sqrt{2-2\cos\frac{\theta}{n}})=\theta$$<br /> So the mouse cannot save it's own hide by making gradual turns instead of sharp ones.<br /> <br /> By directly chasing the mouse,the cat will catch it in a finite amount of time.[/tex]

 

[Bartholomew]

Yes, the interior of the circle.

But no, Nate, what you describe is exactly the strategy I used to refute Dave. The mouse runs tangentially and the cat can never fully close. The closer the cat gets to the mouse, the nearer the cat's radius is the mouse's radius, and the less extra speed the cat has at his disposal. The cat can only catch the mouse given infinite time using this strategy.

 

[RandallB]

The cat first moves to the center of the circle
Then moves to the mouse along the radius to the mouse.
Unless the mouse moves left or right then the cat follows along the cord perpendicular to the starting radius. Cutting across new radius’s
If the mouse turns cat also turns but follows cord from radius at the turn.
Once the mouse hits the perimeter when the mouse goes left or right cat must angle direction off the cord to go closer to the mouse since the cord is shorter than the perimeter. Continuing follow any turn of the mouse it must eventually be “cornered” and caught.

 

[Bartholomew]

Let's say that the cat and mouse start separated by a distance $d$ and the cat's strategy is simply to go towards the mouse's current location. Since the cat is always going to be moving towards the mouse at least as fast as the mouse is moving, it will never loose distance. Clearly, if the mouse must run in a direction that is generally away from the cat.

Now, whenever the mouse turns an angle $\theta$ in time $t$, the cat gains approximately:
$$st(1-\sqrt{2-2\cos\theta})$$
on the mouse, where $\theta$ is the angle that the mouse turns though and $t$ is the time increment. Because the mouse is trapped in the circle, it must travel through an angle of $2\pi$ for every $2\pi r$ distance it moves.

Now, from the equation above it's clear that the mouse wants to make small turns rather than sharp ones so let's take a look at gradual changes:
Let's say that the mouse makes $$n$$ turns of angle [tex]\frac{\theta}{n}[/itex] over time $$t$$<br /> then the cat gains<br /> $$\lim_{n\rightarrow\infty} \frac{1}{n} \times n \times (1 - \sqrt{2-2\cos\frac{\theta}{n}})=\theta$$<br /> So the mouse cannot save it's own hide by making gradual turns instead of sharp ones.<br /> <br /> By directly chasing the mouse,the cat will catch it in a finite amount of time.[/tex]

[tex] <br /> Nate, please make a new post rather than editing your old one. For the benefit of recent readers... Nate's mathematical detail was not present when I replied to him previously. Also, his current proposed solution (cat directly chases mouse) is new; his old one was: cat stays on the radius the mouse is on.<br /> <br /> <blockquote data-attributes="" data-quote="NateTG" data-source="" class="bbCodeBlock bbCodeBlock--expandable bbCodeBlock--quote js-expandWatch"> <div class="bbCodeBlock-title"> NateTG said: </div> <div class="bbCodeBlock-content"> <div class="bbCodeBlock-expandContent js-expandContent "> $$st(1-\sqrt{2-2\cos\theta})$$ </div> </div> </blockquote>First, how did you derive this equation? And you never define s.<br /> <br /> Second, the equation is wrong because it has no term to account for the fact that when the cat gets closer to the mouse, his radius of rotation becomes larger, so he gains on the mouse more and more slowly.<br /> <br /> <br /> Randall: You may have the right idea but I don't understand exactly what you mean. "but follows cord from radius at the turn"... "cat must angle direction off the cord"... "the cord is shorter than the perimeter"... I don't understand what you mean in these phrases.[/tex]

 

[chronon]

Take the radius of the circle to be R and the speed of the cat and mouse to be v. Then:

The cat starts from the centre and always stays on the radius from the centre to the mouse. Suppose the mouse is running round the circumference with speed v, so the cat must maintain an angular velocity v/R (if the mouse changes direction then so does the cat). If the cat's can move outwards so that its radial position is r=R*sin(vt/R). ( Radial velocity is v*cos(vt/R) and the tangential velocity is r*angular velocity = v sin(vt/R), so the resultant speed is v). Thus the cat reaches the mouse when sin(vt/R)=1 that is at time t=R*pi/(2v)

 

[Bartholomew]

At this point I am starting to suspect that I may be wrong. However:

the tangential velocity is r*angular velocity = v sin(vt/R)

r * angular velocity = r * v / R. Where do you get sin(vt/R) from r / R? Also, how are you getting the radial position?

I also took a stab at the math here. To simplify I assume that the circle is a unit circle and the cat and mouse move at speed 1. If the cat is at radius r, he must be moving proportionately fast to keep pace with the mouse's rotational speed. So he moves rotationally at a speed of r. I used the pythagorean formula to get his radial speed. (radial speed) ^2 + r^2 = 1. So radial speed = (1 - r^2) ^.5. Radial speed is dr/dt, so dr/dt = (1 - r^2) ^ .5. Unfortunately I don't know enough calculus to find his radial position from that. Someone else maybe?

 

[NateTG]

Nate, please make a new post rather than editing your old one. For the benefit of recent readers... Nate's mathematical detail was not present when I replied to him previously.

Sorry - I started making a 'small' correction and got carried away...

First, how did you derive this equation? And you never define s.

Let's say that the mouse makes a turn of angle $\theta$ at the midpoint of some time segment of length $2t$. Then the (directly chasing) will, more or less, be running along the third leg of a triangle. The law of cosines:
$$c^2=a^2+b^2+2ab\cos\theta$$
Gives us the relative lengths of the three legs of this triangle. Solving for c
$$c=\sqrt{a^2+b^2+2ab\cos\theta}$$
Now there's a couple of potentially illegitemate simplifications.
Now
$$a+b-c$$
is the difference in the distances that the two had to travel. So it's the amount that the cat gains on the mouse.
$$a+b-\sqrt{a^2+b^2+2ab\cos\theta}$$
I made the simplifying assumption that both legs of the triangle have the same length, and that they're equal in length to $st$ the speed of the cat and mouse, multiplied by some length of time. This simplifies to
$$st(2-\sqrt{2+2\cos\theta})$$
(Which is different than what I have above.)
Now, if we look at the possibility of many small turns over time, rather than one large turn...
$$\lim_{n\rightarrow\infty}s n\times\frac{t}{n} \left(2 - \sqrt{2+2\cos\frac{\theta}{n})\right$$
Which does go to zero - so direct chasing will not work, and the previous derivation was flawed.

Second, the equation is wrong because it has no term to account for the fact that when the cat gets closer to the mouse, his radius of rotation becomes larger, so he gains on the mouse more and more slowly.

Actually, in either version, the $\theta$ would get smaller or the $t$ would get larger for a larger radius of curvature.

 

[RandallB]

Randall: You may have the right idea but I don't understand exactly what you mean. (1)"but follows cord from radius at the turn"...

(2)"cat must angle direction off the cord"..because. "the cord is shorter than the perimeter"... I don't understand what you mean in these phrases.

The mouse can maitain his distance from the cat by following a similar BUT SHORTER cord father out on the radius AND hit the edge first - SO - IF the mouse turns around so does the cat BUT on the new cord perpendicular to the radius difined by where the cat is now! {thats (1) }

Again the only way the mouse can mantain the separation is to follow another similer and even shorter cord! Sooner rather than later the mouse will hit the wall. then the only way the mouse can keep a maximum distance is to stay on the wall until it can past the cord that the cord the cat is maneuvering on.

BUT once the mouse is on the wall, the distance cat to travels on the cord is shorter than the mouse travels on circumference. Therefore cat could overrun the mouse ...SO..(2)"cat must angle direction off the cord' toward mouse of course. Thus from the basic geometry of "the cord is shorter than the perimeter" outlined by that cord, the mouse is cornered and cannot get past the cat.

Like you said in the first post just takes a little reasoning no math needed.

 

[Bartholomew]

Sorry - I started making a 'small' correction and got carried away...

Okay, sorry.

I can't picture the situation you're setting up--the midpoint of a time 2t? I don't understand what the parts of your triangle are. Theta is--the angle the mouse travels through in 2t. c is--the (approximately straight) path the cat takes towards the mouse in 2t. Do I have that right? So what are a and b?


Okay, I see what you mean, Randall. (it's spelled "chord" though that wasn't the source of my confusion)

You definitely are thinking about the same things I came up with, but there is an option for the mouse that you may have overlooked. After he hits the wall traveling on his chord, the mouse can simply turn around on the _same_ chord he came on. What would you have the cat do in that situation? If he tries to get closer to the mouse then the mouse can get past the cat's chord. If the cat follows on his own previous chord then it seems he gains no ground. (There is something the cat can do)

Actually, to be honest, I am not positive of the answer of this teaser. I know the cat can corner the mouse, but his tactics become less effective as the two approach the edge of the circle and the edge becomes more approximately straight. There is a trade-off here, though, between the straightness of the edge and the relative speed of the cat and mouse--as you zoom in the edge gets straighter but the cat and mouse get faster. So it seems still a toss-up. I'll try and think it through today.

 

[chronon]

r * angular velocity = r * v / R. Where do you get sin(vt/R) from r / R? Also, how are you getting the radial position?

I'm starting from the assumtion that r=R sin(vt/R), and showing that this gives a speed v.

So he moves rotationally at a speed of r. I used the pythagorean formula to get his radial speed. (radial speed) ^2 + r^2 = 1. So radial speed = (1 - r^2) ^.5. Radial speed is dr/dt, so dr/dt = (1 - r^2) ^ .5. Unfortunately I don't know enough calculus to find his radial position from that. Someone else maybe?

dr/dt =(1-r^2)^.5 suggests a trigonometric substitution for r. That's what I did to get to r=sin(vt/R).

 

[RandallB]

you may have overlooked. After he hits the wall traveling on his chord, the mouse can simply turn around on the _same_ chord he came on. What would you have the cat do in that situation? If he tries to get closer to the mouse then the mouse can get past the cat's chord. If the cat follows on his own previous chord then it seems he gains no ground. (There is something the cat can do)

Of course there is something the cat can do - keep doing the same thing- turn when the mouse does but use the new chord as already planned.
If the mouse uses his "old " chord - well it intersects with the chord the cat is now using - and after the turn the cat is starting from the right angle of the triangle - so the cat has the shorter path - the mouse is not going to get past.
Any adjustment, as in (2), to avoid overruning the mouse is of course toward the mouse.

Another way of saying the same thing - cat stays on a radius line from center to the mouse however the mouse moves. Any surplus speed not needed to stay on that line is used to go out not in on the line.

Zooming has no affect - they have the same speed.

 

[Bartholomew]

(Chronon: I'll reply to you later, I don't have a lot of time now)
Randall, if the mouse returns along his own chord and the cat picks a different chord which intersects the mouse's chord, in order to move closer to the mouse, then the mouse will reach the intersection point before the cat does since the mouse is not expending speed on moving towards or away from the cat. If you draw the chords you will see that the cat's distance to the intersection point of the two chords is longer than the mouse's distance.

Their speed increases in the viewing window as you zoom in. Of course it is still the same speed, but relative to the window it is greater--and also relative to the window the circle's edge becomes flatter, which means that the cat's tactics, which are based on the curvature of the circle, become less effective. I still haven't worked out just what happens.

 

[NateTG]

Actually, to be honest, I am not positive of the answer of this teaser. I know the cat can corner the mouse, but his tactics become less effective as the two approach the edge of the circle and the edge becomes more approximately straight. There is a trade-off here, though, between the straightness of the edge and the relative speed of the cat and mouse--as you zoom in the edge gets straighter but the cat and mouse get faster. So it seems still a toss-up. I'll try and think it through today.

There are other strategies that the cat can use:

For example:
If the mouse is running away from the cat, that is, the heading of the mouse is within, say 60 degrees of the heading from the cat to the mouse, then the cat runs with the same velocity as the mouse.
If the mouse is running 'perpendicular' - that is, the angle that the heading of the mouse makes with the heading of the cat towards the mouse is more than 60 degrees and less than 120 then the cat goes, more or less, directly after the mouse.
If the mouse is running towards the cat (the remaining cases), then the cat 'mirrors' the mouses movement so that it intercepts on the perpendicular bisector between the two if possible, and chases directly after the mouse otherwise.

It's quite clear that the rate at which the cat closes in the latter two cases can be bounded below by .4 times the cat's speed (there's probably a better angle - but I don't care so much.) It's also clear that using this strategy, the cat never looses distance on the mouse. So the only potential strategy the mouse has is to run in such a way that the total time it spends in those two states is bounded. This means that the mouse must run straight in more or less straight segments followed by ever tighter turns. (It can't run straight forever because of the bounding circle.)

 

[AKG]

Let the cat be at the center and the mouse be at the top (this is a reasonable initial condition). The cat will match the mouse's horizontal movement precisely, and match it's vertical movement in magnitude, but the direction will always be up. If the mouse makes "nice" moves, the cat is bound to catch him in finite time. The cat will always be on the same vertical as the mouse, but will be on closer and closer horizontals as time passes since the mouse can't move upwards forever (assuming "nice" moves).

However, what if the mouse doesn't make nice moves? What if it just goes left and right forever, or moves upwards but such that it's upwards component of motion decreases at an exponential rate so that it reaches the top of the circle (after moving down from it a bit initially) "after" infinite time? A different heuristic would be required to solve this one. Perhaps the cat should commit to making some upwards progress each time (if the mouse moves vertically, up or down, then this no problem, the cat just has to do what it does in the "nice" case), and if the mouse just moves sideways, the cat, after some time, compensates for this by simply moving sideways until it has realigned itself to be on the same horizontal as the mouse. I believe this will eventually lead to a capture.

But what if the mouse converges towards the top, but doesn't reach it? In fact, it doesn't have to be the top, it can be any point that is less than half-way between the cat and mouse, and it will give the cat problems if he acts as though it were the "nice" case. Perhaps, after some fixed amount of time, or after some fixed distance has been travelled, the cat must take a steeper path to the top, again losing its position on the same horizontal as the mouse. However, it should be able to do this in such a way that it can recover without the mouse escaping past him. I'll have to think some more if I want this to be more rigourous, but I think this gives good reason to believe that the cat can catch the mouse.

 

[RandallB]

Randall, if the mouse returns along his own chord and the cat picks a different chord which intersects the mouse's chord, in order to move closer to the mouse, then the mouse will reach the intersection point before the cat ... . draw the chords you will see that the cat's distance to the intersection point of the two chords is longer ...

Their speed increases in the viewing window as you zoom in.

Obviously you didn’t have time to draw this yourself before telling me too.
The Cat isn’t picking just any chord when the mouse turned back on his old chord!
He follows the same first rule and goes on the new perpendicular (right angle) to the radius that runs from center to cat to mouse. If the mouse turns back on the old line that put him on the hypotenuse – don’t need to draw it to know the cat has the short line.

“ZOOM IN” What has this got to do with anything!
Let’s test it, can you be our subject? We’ll have you jump off an eight story building! But half way down we’ll ZOOM IN! Now after two more Levels you still have half way to go! Great let's ZOOM IN Again! Need to go another full floor just to get to half way again. You might be OK, let's ZOOM IN again! Sure thing you have a long way to go it seems, we’ll just keep ZOOMING IN! One foot to go – no problem – just keep ZOOMING IN! ----- Do me a favor, use a chair for your first test jump – let use know if you never make it to the floor.
RB

 

[Bartholomew]

No, after the cat parallels the mouse for a while on his chord, he is no longer on the same radius from the center as the mouse is.

The zooming in has to do with the curvature of the circle. When the cat and mouse are very close to the circle wall, the cat's tactics do increasingly little, in terms of percentage of the distance he needs to gain over the actual percentage he does gain in any iteration of the chase.

The flip side is, the iterations start to take less time. This is what it means to say that when you zoom in, they speed up.

I believe now that the cat can never catch the mouse; I will later post my explanation.

 

[Alkatran]

Trap the mouse.

The cat's strategy:
Define X axis perpendicular to line intersecting mouse and cat
Always keep cat X close enough to mouse X to stop mouse from escaping
Move closer when possible

Alright, so let's start this off in the worst situation:
The cat is at the bottom of the circle, the mouse is above it.

If the mouse stays stil, move towards it
If the mouse moves right, travel along the circumeference right (the mouse can't get past the cat because it will be further to the right.
Same for left
continuing...
If the mouse changes direction, begin moving towards mouse (distance decreases) until you need to move side to side to keep the blocking potential
Repeat until you reach center...

Now the cat is at the center and the mouse is higher up. The mouse must always be moving or the cat can simply close in. If the mouse moves backwards the area it has available decreases. The mouse can move forward, but that would accomplish nothing. If the mouse moves sideways the cat moves sideways until the mouse hits the side of the circle: the cat can now close in further on the mouse. If the mouse changes direction the cat gets a big potential to close in.



The only problem arises at the very end: at the top where the circle arc begins more like a line and makes closing in almost impossible. EXCEPT that the mouse MUST change direction or hit the cat.

 

[RandallB]

No, after the cat parallels the mouse for a while on his chord, he is no longer on the same radius from the center as the mouse is.

That was the first rule - stay on the radius that goes from the center to the mouse any travel on "the chord" that 'overruns the mouse is adjusted toward the mouse.

Here - I'll make your proof EZ for you:
Cat first ignores the mouse goes to center.
Wherever you place mouse at that time draw the chord (Diameter) that is perpendicular to the radius the runs to the mouse.
IF you get the mouse to even cross that diameter line – I’ll concede and your right.

No “SPEED” needed just equal length steps taken by each.
Count them, then set any 'speed' you like. Mouse may turn on every step.
CAT only follows two rules:
1)Step to the line that keeps cat inline with center and the mouse.
2)If more than one spot fits length of step on described line – use the one closer to the mouse.
That's it. Stepping over the mouse is a kill.

Good luck – ZOOM all you want.

 

[Bartholomew]

If the cat always stays on the radius between the mouse and the center, then it takes infinite time to catch the mouse; I gave the formula for this situation in a previous post: dr/dt = (1 - r^2) ^ .5 is the speed at which the cat closes on the mouse, when the mouse is at the edge of the circle with radius 1 and the cat is r units from the center.

I thought you wanted to have the cat do something more complicated, but I guess I misinterpreted you.

 

[chronon]

If the cat always stays on the radius between the mouse and the center, then it takes infinite time to catch the mouse; I gave the formula for this situation in a previous post: dr/dt = (1 - r^2) ^ .5 is the speed at which the cat closes on the mouse, when the mouse is at the edge of the circle with radius 1 and the cat is r units from the center.

r=sin(t) is the solution to dr/dt = (1 - r^2) ^ .5, (with r=0 at t=0), so r=1 at t=pi/2.

 

[RandallB]

it takes infinite time to catch the mouse; I gave the formula for this situation in a previous post: dr/dt = (1 - r^2) ^ .5 is the speed at which the cat closes on the mouse,
do something more complicated,

Complicated? Who needs complicated - when simple wins.

Posting a "solution" that dosn't work and say it does - don't mean a thing.
Just translate it to one step at a time, draw it on a piece of paper.
Make the steps 0.1 the distance from cat to mouse. Max steps from center for cat 2.5 times the # of steps to the edge.
Post drawing where the mouse crosses the diameter ever or mouse lasts more than max steps (25 if mouse on edge) & you win!
No need to post till you have a winner ( you won't ).

Put up Or admit cat gets mouse.

 

[Bartholomew]

The cat and the mouse take infinitely short steps. Certainly with a crude drawing the cat might catch the mouse that way.

As the cat's radius of rotation goes to the mouse's radius of rotation (as the cat approaches the mouse), the rate at which the cat approaches the mouse goes to zero. I've shown work for this in an earlier post.

 

[RandallB]

The cat and the mouse take infinitely short steps.

SO WHAT cat is not trying to follow a curve is picking points closer to the mouse!
ZOOMING doesn't work here, any better than jumping off the building.
If your "work" has a solution that can plot lines - they will absolutly merge before the mouse can get half way around. IF not - The work or the assumtion is just wrong.
RB

 

[Bartholomew]

The cat does follow a curve. This is the work:

To simplify I assume that the circle is a unit circle and the cat and mouse move at speed 1. If the cat is at radius r, he must be moving proportionately fast to keep pace with the mouse's rotational speed. So he moves rotationally at a speed of r. I used the pythagorean formula to get his radial speed. (radial speed) ^2 + r^2 = 1. So radial speed = (1 - r^2) ^.5. Radial speed is dr/dt, so dr/dt = (1 - r^2) ^ .5. Unfortunately I don't know enough calculus to find his radial position from that. Someone else maybe?

 

[NateTG]

If the mouse changes direction, begin moving towards mouse (distance decreases) until you need to move side to side to keep the blocking potential
Repeat until you reach center...

The cat can simply move into the center - WOLOG the mouse is directly north of it.

Now the cat is at the center and the mouse is higher up. The mouse must always be moving or the cat can simply close in. If the mouse moves backwards the area it has available decreases. The mouse can move forward, but that would accomplish nothing. If the mouse moves sideways the cat moves sideways until the mouse hits the side of the circle: the cat can now close in further on the mouse. If the mouse changes direction the cat gets a big potential to close in.

What if the mouse moves back and forth left to right without hitting the side of the circle? If the cat matches by moving sideways, the mouse can keep going forever. If the cat does not move side to side, what does it do? The claiming that it can now close in further does not necessarily make it so.

 

[Bartholomew]

r=sin(t) is the solution to dr/dt = (1 - r^2) ^ .5, (with r=0 at t=0), so r=1 at t=pi/2.

How did you find that solution (assuming you're right)?

Edit: Substituting shows you are right! Congratulations! What's the math you used to get that?

 

[Davorak]

I will be back later, I have to go to a review section now. I found a way to prove the cat will catch the mouse even if it does take infinite time. Try thinking of the cat decelerating as it reaches the outer rim as a force. Then use energy conservation to show that the cat can catch the mouse.

I have also completed a few numerical simulations which show that the cat catches the mouse in finite time. The numerical simulations converge. This is not a proof but I would say is fairly conclusive.