Conference rusure::math

Yes - proof : Cat goes to middle of circle.  Now he runs in such a way as to
keep himself directly between the middle of the circle and the mouse.  This
requires at most a radial velocity equal to that of the mouse, and since the
         ^^^^^^^delete
mouse is further out than the cat this corresponds to a lower speed than the
mouse.  The excess speed is used in the direction straight toward the mouse.

This means that the cat is always between the centre of the circle and the
mouse, and is travelling outwards.  

Now - this algorithm gives a spiral heading outward.  But mice have finite
width hence the cat will catch the mouse at the point where this spiral
crosses the inside edge of the mouse's track, a finite distance in.

If the mouse was infinitismal, the cat wouldn't bother trying to catch it.
                 ^^^^^^^^^^^^wrong spelling, me thinks - Stan no doubt will
provide the correct spelling.


Now - for the more interesting question about two points....


/Bevin

infinitesimal

Brett's algorithm shows that the (0-dimensional) cat can keep getting closer
and closer to the (0-dimensional) mouse.  But near the boundary of the circle,
it seems to make less progress in getting closer to the mouse.

Can it get infinitesimally (thanks, Stan) close to the mouse in a finite amount
of time?

Easily. Let the cat be a distance d from the mouse along the radius, where
the mouse runs along the circumference. Then if the cat chooses a path along
an imaginary circle with the same radius and centered along the radius
vector at distance (2r-d) from the center of the real circle, then cat and
mouse are on a collision course and will meet after travellingOr

PIr/6 units. Another way of looking at the problem is for the cat to look
in an imaginary mirror halfway between cat and mouse and simply to mimic
the mouse's motion.

Lynn Yarbrough

But that imaginary mirror keeps moving, too, so the distance travelled by the
cat probably isn't pi*r/6, and it's still not clear whether the cat can get
"infinitely close" in a finite amount of time.

In this diagram, O is the center of the circle,		O
M is the mouse (on the edge of the unit circle),	|\
and C is the cat (at distance R from the center		| \
of the circle, on a radius connecting O and M).		|  \
							|   \
If the mouse an infinitesimallly small distance dT	C    \
along the circumference of the circle, then the cat	|     \
(which is also moves distance dT, and stays on a	|      \
radius connecting O and M) can get closer to the	|	\
mouse by distance dR, where dR is given by:		|	 \
							M
	(dR)^2 + (R dT)^2 = (dT)^2
or
	     dR
	----------- = dT
	sqrt(1-R^2)

Integrating both sides, we have:

	asin(R) = T + k
or
	R = sin(T+k)

Thus, if the mouse limits itself to the circumference of the circle, then the
cat's path describes an arc of a circle with radius 1/2, and can catch the
mouse after travelling a distance pi.

					- Gilbert

However, let us not so constrain the poor mouse.  Instead, let's assume the cat
uses the same strategy (cats being what they are), and let the mouse simply stay
a (small) distance e from the cat, moving in a near-circle, or spiral.  Then:

		  R dt
	(dR)^2 + (-----)^2 = (dT)^2
		  R + e
or
	     (R + e) dR
	------------------- = dT
	sqrt(2 e R + e ^ 2)

Integrating both sides, we have:

	(R + 2 e) sqrt(2 R + e)
	----------------------- = T + k
	        3 sqrt(e)

When will the mouse finally be forced to the circumference of the circle?
That is, for what T will R + e = 1?

	    (1 + e) sqrt(1 + R)
	T = ------------------- - k
		3 sqrt(e)

or (if e << 1)

	    sqrt(1 + R)
	T = ----------- - k
	     3 sqrt(e)

This shows that the mouse, by an appropriatly small choice of e, can make the
distance travelled (and thus the time until capture) arbitrarily large.

					- Gilbert

If the mouse is not on the circumference, its optimal course is to run
directly away from the cat. However, that shortly brings it to the edge, 
whereupon the cat adopts the circular-arc path I described. If the cat 
takes a suboptimal strategy, of course it may take forever. All  the cat
has to do is stay on the same radius vector as the mouse, after which the
mouse can only travel a sixth of the circum. before being caught.

To amplify on the mirror analogy: yes, the mirror moves, but toward the mouse,
and the points where the mirror meet the circle are the limits of the distance
the mouse can move before being caught. As the mirror moves toward the edge
the mouse is more confined, until cat, mouse, and mirror coincide.

Lynn Yarbrough

To shatter the mirror analogy, let the mouse simply run at full speed left, and
then full speed right, a small distance away from the mirror.  The poor cat, in
mimicking the left-right motion of the mouse, has no velocity component to apply
to reducing the distance between itself and the mirror, or similarly, the mouse.

					- Gilbert

This problem reminds me of Zeno's paradox.  Hence I vote for the cat.

Not the most rigorous of proofs, but what do you expect from a broken mirror?

					John

Unfortunately (for the mouse), its path is not a straight line - it is the
circumference of a circle. Thus as it moves along the circumference it has
a component in the direction of the mirror, which in turn brings it closer to 
the cat.

Incidentally, this problem falls into the category of "Differential Games",
which are well treated in a book by that title written by Rufus Isaacs.

Lynn Yarbrough

Why must the mouse be constrained to move on the circumference of the circle?
FIRST, let the mouse approach the "mirror" a little, THEN let it do the left-
right dance parallel to the mirror, which the cat so obligingly duplicates.

					- Gilbert

For what it's worth, ...

A simulation of the cat mouse problem was done.

The cat started at the center of the circle, the mouse midway between the
cat and the circumference.

The cat's strategy was to stay on the same radius as the mouse.
The mouse's strategy was to spiral outward around the circle (an equiangular
spiral, that is, the angle between a tangent of the spiral and the radius
remains constant).

The radius of the circle is 1, the "step" size (this is a quantum operation,
remember?) is 10^-5, and angle for the equiangular spiral is pi/2 - 0.04.

The cat caught the mouse at a distance 0.579142 from the center, after both had
travelled a distance of 1.97861.

Although this doesn't prove anything one way or the other about the continuous
case, it gives a lower bound on the distance travelled before the cat catches
the mouse (if ever).  This lower bound is 1.97861 + (1.0 - 0.579142), since the
mouse could've headed directly away from the cat just before being caught in
this simulation, or 2.399468.

If we assume that this is the cats best strategy, then this demonstrates that
the mouses best counter-strategy is NOT to run straight away from the cat, and
stay on the circumference until being caught, since that strategy allows the
mouse to travel only 1/2 + pi/3, or 1.04719 units.

					- Gilbert