NY Times math problem

[Rich Grise]

DId anyone here see the problem presented in
the Science section of NY Times last week?

No. Got a link?

Thanks,
Rich

 

[Rich Grise]

Riddle:

There is a rabbit in the middle of a perfectly circular pond. An
agent is trying to get the rabbit. The rabbit swims exactly away from
the agent. After a few seconds, the agent's head explodes. Why?

Is the "agent" wading/swimming, or just walking around the perimeter
of the pond? What's each of their respective speeds? How did the rabbit
get to the middle of the pond in the first place? Was somebody using him
for Muxkie bait? ;-)

Thanks,
Rich

 

[Rich the Cynic]

The rabbit is in the middle of a circular pond. The agent is on the edge of
the pond. The agent can run 4-times as fast as the rabbit can swim. Can the
rabbit get away ?

It doesn't have to. All it needs to do is float there until the agent dies
of exhaustion from running around and around the pond forever. >:->

Hope This Helps!
Rich

 

[erg]

Riddle:

There is a rabbit in the middle of a perfectly circular pond.  An
agent is trying to get the rabbit.  The rabbit swims exactly away from
the agent.  After a few seconds, the agent's head explodes.  Why?

Ya know, if the agent always seeks the closest path (with no
underlying intelligence to escape the following scenario), the rabbit
(if it were more intelligent) could follow a zig-zag path.  As soon as
it moves somewhat to the right, the agent sees this and moves in that
direction.  The rabbit, noticing the reduced distance, changes
direction immediately.  As it crosses the diameter the agent is
standing on, the agent reverses direction.  The opposite then happens,
ad nauseum, until the rabbit reaches the shore safely.

Theorem 1: The rabbit can reach the shore regardless of the agent's
relative speed.
Theorem 2: Either the agent's head explodes, or the Church-Turing
Theorem is false.

Theorem 2 follows from taking the limit as delta x approaches zero
(that is, the width of the zig-zag).  In the limit, the rabbit appears
to proceed in a straight line, exactly opposite the agent (this also
works if the rabbit simply moves in exactly this path, with no
infinnitessimal shaking).  The agent cannot decide which direction to
go, because his distance-o-meter is saying both directions are equal.
In terms of angle, sign(tangent(theta)) is undefined (where sign(x) is
+1 when x > 0, -1 when x < 0, and either 0 at x = 0, although sign(0)
may sometimes defined as +1).  So now it's an undecidable problem, and
if the agent somehow succeeds, a lot of theorems (including those
about decidability) are wrong, or the agent's head simply
explodes. ;-)

_I_ would award your solution the prize, at any rate.

At least it forces us to make the agent's strategy explicit.

 

[William Hughes]

Riddle:

There is a rabbit in the middle of a perfectly circular pond. An
agent is trying to get the rabbit. The rabbit swims exactly away from
the agent. After a few seconds, the agent's head explodes. Why?

Ya know, if the agent always seeks the closest path (with no
underlying intelligence to escape the following scenario), the rabbit
(if it were more intelligent) could follow a zig-zag path. As soon as
it moves somewhat to the right, the agent sees this and moves in that
direction. The rabbit, noticing the reduced distance, changes
direction immediately. As it crosses the diameter

No, if the rabbit is far enough from the center of the circle
it cannot swim fast enough to cross the diameter so the agent
does not have to change direction. Indeed the agent's optimal
strategy is to
always seek to minimize the angular separation.

the agent is
standing on, the agent reverses direction. The opposite then happens,
ad nauseum, until the rabbit reaches the shore safely.

Theorem 1: The rabbit can reach the shore regardless of the agent's
relative speed.
Theorem 2: Either the agent's head explodes, or the Church-Turing
Theorem is false.

Theorem 2 follows from taking the limit as delta x approaches zero
(that is, the width of the zig-zag). In the limit, the rabbit appears
to proceed in a straight line, exactly opposite the agent (this also
works if the rabbit simply moves in exactly this path, with no
infinnitessimal shaking). The agent cannot decide which direction to
go, because his distance-o-meter is saying both directions are equal.

Nope. The agent knows that there are two optimal strategies.
The agent knows that it is suboptimal
not to choose between the two optimal strategies, but the method of
choice
is arbitrary. The agent will choose one of the optimal strategies
(either at random
or by some arbitrary rule, e.g. alphabetical order).


- William Hughes

 

[riverman]

Which shows, I think (to return to the very original question about
whether this needs horrible maths to solve) that there is a simple proof
that pretty-well anyone can follow that shows the rabbit can escape in
the specific case (it goes to where it can just swim faster than the
agent, swims round in a circle until it gets to 180 degrees away from
the agent, and can then make it to the shore faster than the agent can
run round), but that the optimum strategy, and hence the answer to the
unasked question about which size of ponds or relative speeds allow the
rabbit to escape do require the horrid maths.
--
Online waterways route planner:http://canalplan.org.uk
           development version:http://canalplan.eu- Hide quoted text -

- Show quoted text -

I'm not convinced about the 'keep the agent on the opposite side'
logic. Lets expand the problem to their being TWO agents, already on
opposite sides. If the rabbit swims in any direction, off-center, then
both agents will move together to be at the point the rabbit is
apparently aiming for, then the rabbit moves slowly back towards
center and the problem is reduced to the original one. So the rabbit
can escape with TWO agents around the pool...or even an INFINITE
number of them? (well, slightly less than infinite, in this case....)

--riverman

 

[Sylvia Else]

I'm not convinced about the 'keep the agent on the opposite side'
logic. Lets expand the problem to their being TWO agents, already on
opposite sides. If the rabbit swims in any direction, off-center, then
both agents will move together to be at the point the rabbit is
apparently aiming for, then the rabbit moves slowly back towards
center and the problem is reduced to the original one. So the rabbit
can escape with TWO agents around the pool...or even an INFINITE
number of them? (well, slightly less than infinite, in this case....)

When the rabbit moved back towards the centre of the pool, the agents
would move back to positions oppoisite each other.

It appears that the rabbit cannot escape if there are two agents.

Sylvia.

 

[Tim Little]

Lets expand the problem to their being TWO agents, already on
opposite sides. If the rabbit swims in any direction, off-center,
then both agents will move together to be at the point the rabbit is
apparently aiming for

No, that is not their best cooperative strategy even if it would be
their best strategy individually. Though actually it is not even
their best individual strategy, as the rabbit could then dictate which
direction they run with arbitrarily little cost by "feinting" motion
toward any arbitrary point on shore.


- Tim

 

[William Hughes]

When the rabbit moved back towards the centre of the pool, the agents
would move back to positions oppoisite each other.

They may not have time.

It appears that the rabbit cannot escape if there are two agents.

Assume that the two agents are unaware of each other's existence and
choose the optimal strategy for a lone agent (always move so as
to decrease the angular difference). The rabbit must very slightly
modify his strategy, keep almost but not quite 180 degrees from the
agents
(otherwise they might split up). In this case the rabbit escapes.

However, assume that the two agents are aware of each other's
existence
but cannot communicate. They can stop the rabbit escaping. They
divide the
circle in two halves. Each agent adopts the strategy, move toward the
point
in my half that is closest to the rabbit.

- William Hughes

 

[riverman]

their best individual strategy, as the rabbit could then dictate which
direction they run with arbitrarily little cost by "feinting" motion
toward any arbitrary point on shore.

- Tim

The 'feinting' move would only work while the rabbit is extremely
close to the center. The strategy for any agent is to determine the
point that the rabbit is aiming for, and make haste toward that point.
While the rabbit is very close to the center, 'feinting' merely moves
it around a circle with a small radius, and changes the targetted
landing zone immensely with each 'feint'. But its a moot point: the
rabbit cannot make a break for the shore from the center...it needs to
be somewhere along a circle of a larger radius, which is where feints
become less productive.

The agent, meanwhile, would always race along the perimeter arc that
is shortest from where he is to where the rabbit is headed (if the
rabbitwere going directly along a radius). If the rabbit gains enough
on the agent that the arclength 'behind' him is suddenly shorter than
the one he is travelling along, he should turn around.

I think the rabbit could make use of this to follow a sinusoidal
pattern to the shore, always jogging back across the 'opposite radius'
to the position of the agent, causing the agent to reverse course.

In fact, if the rabbit were able to run in ANY circle until it were
precisely opposite the agent, the agent would be faced with two
equally desirous paths, and might even freeze in place instead. It
would if it were a robot programmed to follow the shortest arc to the
rabbit's landing zone...

 

[Tim Little]

The 'feinting' move would only work while the rabbit is extremely
close to the center.

It works everywhere, as you later post:

I think the rabbit could make use of this to follow a sinusoidal
pattern to the shore, always jogging back across the 'opposite radius'
to the position of the agent, causing the agent to reverse course.

Yes, this is exactly why the "aim point" strategy fails. The rabbit
can make the agent run back and forth like a cat chasing the dot from
a laser pointer.


Though the reasoning is more general than that: at any time, the
situation is completely determined by the distance between rabbit and
shore, and the center angle between rabbit and agent. For a given
angle, closer to shore is always better for the rabbit. For a given
distance, a smaller angle is always better for the agent. If the
agent ever voluntarily increases the angle, the rabbit's position is
needlessly improved.


- Tim

 

[BartC]

DId anyone here see the problem presented in
the Science section of NY Times last week?
Quite startling, to see something so sophisticated
in a 'general readership' publication.

Is it solvable without a calculus of variations approach?

It's possible they only expected the readership to be aware of 2-pi-r and to
assume the rabbit will swim direct towards the shore away from the agent. In
that case the general reader can say the rabbit cannot escape. Which was my
first thought..

I don't like these spiraling paths and looked at the probability of escaping
if the rabbit swam in a straight line, invisibly under water.

But I only made that odds of 50% of escaping, if the rabbit avoided the
point on the shore +/- 50 degrees opposite the agent. Not so good. And that
assumes the agent will start running around the pond.

 

[[email protected]]

It's possible they only expected the readership to be aware of 2-pi-r and to
assume the rabbit will swim direct towards the shore away from the agent. In
that case the general reader can say the rabbit cannot escape. Which was my
first thought..

I don't like these spiraling paths and looked at the probability of escaping
if the rabbit swam in a straight line, invisibly under water.

But I only made that odds of 50% of escaping, if the rabbit avoided the
point on the shore +/- 50 degrees opposite the agent. Not so good. And that
assumes the agent will start running around the pond.

There is an interesting book on this stuff:

"Chases and escapes: The Mathematics of Pursuit and Evasion," Paul
J. Nahin, Princeton University Press, 2007, ISBN-13:
978-0-691-12514-S, ISBN-10: 0-691-12514-7.

Pp. 78 references "Houghton's Problem: A circular Pursuit That Is
Solvable in Closed Form."

So, there, 8^).

John

 

[William Hughes]

It works everywhere, as you later post:


Yes, this is exactly why the "aim point" strategy fails.

It is not clear what the "aim point" is. If it is defined as the
intersection
of the tangent of the rabbit's path with the circle, then if the agent
always runs toward the aim point then the rabbit can escape
(even if the agent is very fast). But this
assumes a stupid agent (e.g. if the rabbit is close to shore it can
make the agent run away from it by swimming slowly toward the center).
If the agent chooses a simpler strategy, run in the direction that
decreases
the angular separation (if the angular separation is 0, do not move;
if the angular separation is 180 degrees, run clockwise)
then the rabbit cannot cause the agent to reverse
direction if the rabbit is more than 1/4 of the radius from the
center.
Indeed this second strategy is easily seen to be optimal for the
agent.

- William Hughes

 

[legg]

It's possible they only expected the readership to be aware of 2-pi-r and to
assume the rabbit will swim direct towards the shore away from the agent. In
that case the general reader can say the rabbit cannot escape. Which was my
first thought..

I don't like these spiraling paths and looked at the probability of escaping
if the rabbit swam in a straight line, invisibly under water.

The cartoonist Sam Gross might suggest that the rabbit expire,
escaping to bunny heaven. That's what the befuddled scientist's
laboratory mice did, in one published work.

RL

 

[Tim Little]

then if the agent always runs toward the aim point then the rabbit
can escape (even if the agent is very fast). But this assumes a
stupid agent

Yes it does, which is exactly why I was arguing that it was a poor
strategy for the agent to employ.


- Tim

 

[riverman]

It is not clear what the "aim point" is.  

Good point. I had an intuitive understanding for what I meant, but
upon closer introspection, I see that it is not clearly stated.

What about "the intersection of the radius containing the rabbit and
the edge of the pool, regardless of the direction of the rabbit's
motion"? Would aiming for that be synonymous to the strategy of the
agent moving to decrease the angular separation (between the rabbit
and the tangent line that defines the instantaneous direction of
motion of the agent?). What about just saying 'the agent moves to
minimize the distance between himself and the rabbit'?

--riverman

 

[Jim Thompson]

DId anyone here see the problem presented in
the Science section of NY Times last week?
Quite startling, to see something so sophisticated
in a 'general readership' publication.

Is it solvable without a calculus of variations approach?

I've not done anything on paper, but isn't this simply a variation of
the pursuit curve problem... the rabbit swims along a vector defined
by the agent's position and the center-point of the pond?

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona 85048 Skype: Contacts Only | |
| Voice480)460-2350 Fax: Available upon request | Brass Rat |
| E-mail Icon at http://www.analog-innovations.com | 1962 |

Stormy on the East Coast today... due to Bush's failed policies.

 

[Jim Thompson]

That must be a super rabbit, to keep swimming like that.

We have a jackrabbit in the neighborhood. I see him every morning
running along the ridge as I'm pouring my coffee ;-)

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona 85048 Skype: Contacts Only | |
| Voice480)460-2350 Fax: Available upon request | Brass Rat |
| E-mail Icon at http://www.analog-innovations.com | 1962 |

Stormy on the East Coast today... due to Bush's failed policies.

 

[William Hughes]

Good point. I had an intuitive understanding for what I meant, but
upon closer introspection, I see that it is not clearly stated.

What about "the intersection of the radius containing the rabbit and
the edge of the pool, regardless of the direction of the rabbit's
motion"?

A useful point, but the name "aim point" seems odd
as the point has no dependence on the direction of the rabbit's
motion. (It is certainly not the meaning that Tim Little
ascribes to "aim point")

Would aiming for that be synonymous to the strategy of the
agent moving to decrease the angular separation (between the rabbit
and the tangent line that defines the instantaneous direction of
motion of the agent?).

Yes.

Note:
Angular separation: Take a polar coordinate system centered at the
circle.
The angular separation is the angular difference between the
rabbit's
angular coordinate and the agent's angular coordinate.

What about just saying 'the agent moves to
minimize the distance between himself and the rabbit'?

Equivalent to minimizing the angular separation
(noting that the agent's motion is constrained to be outside or on the
boundary of the disk of radius r, otherwise, as Richard Heathfield
points
out, splash).

- William Hughes