# More cat and mouse

1. Jan 31, 2005

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

Last edited: Jan 31, 2005
2. Feb 1, 2005

### DaveC426913

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.

3. Feb 1, 2005

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

Last edited: Feb 1, 2005
4. Feb 1, 2005

### NateTG

Let's say that the cat and mouse start seperated 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 $$\frac{\theta}{n}[/itex] over time [tex]t$$
then the cat gains
$$\lim_{n\rightarrow\infty} \frac{1}{n} \times n \times (1 - \sqrt{2-2\cos\frac{\theta}{n}})=\theta$$
So the mouse cannot save it's own hide by making gradual turns instead of sharp ones.

By directly chasing the mouse,the cat will catch it in a finite amount of time.

Last edited: Feb 1, 2005
5. Feb 1, 2005

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

6. Feb 1, 2005

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

7. Feb 1, 2005

### Bartholomew

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.

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

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.

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.

8. Feb 2, 2005

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

9. Feb 2, 2005

### Bartholomew

At this point I am starting to suspect that I may be wrong. However:
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?

10. Feb 2, 2005

### NateTG

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

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.

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

Last edited: Feb 2, 2005
11. Feb 2, 2005

### RandallB

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

12. Feb 2, 2005

### Bartholomew

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

13. Feb 3, 2005

### chronon

I'm starting from the assumtion that r=R sin(vt/R), and showing that this gives a speed v.
dr/dt =(1-r^2)^.5 suggests a trigonometric substitution for r. That's what I did to get to r=sin(vt/R).

14. Feb 3, 2005

### RandallB

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.

Last edited: Feb 3, 2005
15. Feb 3, 2005

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

16. Feb 3, 2005

### NateTG

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

17. Feb 3, 2005

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

18. Feb 4, 2005

### RandallB

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 lets ZOOM IN Again! Need to go another full floor just to get to half way again. You might be OK, lets 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

19. Feb 4, 2005

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

Last edited: Feb 4, 2005
20. Feb 5, 2005

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