Connect with us

NY Times math problem

Discussion in 'Electronic Design' started by Mark-T, May 3, 2009.

Scroll to continue with content
  1. Mark-T

    Mark-T Guest

    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?
     
  2. Jake

    Jake Guest

  3. Sue...

    Sue... Guest

  4. Sylvia Else

    Sylvia Else Guest

    Yes.

    Spoiler below 13


    0


    1


    2


    3


    4


    5


    6


    7


    9


    10


    11


    12


    13

    Since the agent can run four times as fast as the rabbit can swim, no
    matter what the agent does, the rabbit can swim away from the centre,
    and keep the agent on the far side as long as the rabbit is no more than
    1/4 of the radius from the centre. So the rabbit can reach a point 3/4
    of a radius from the edge while the agent is still on the opposite side.

    From that point, if the rabbit swims directly to the edge, he has to
    swim 3/4 of a radius. In that time, the agent can run at most 4 times as
    far, or 3 * radius. But the distance to the rabbit's exit point is Pi *
    radius, or a bit further, so the rabbit is free.

    For the second part, instead of 4, write m, and let R be the radius.

    The rabbit can reach a point R/m from the centre while keeping the agent
    opposite. From that point, the rabbit needs to swim R * (m - 1) / m to
    reach the edge. In the available time, the agent can run R * (m - 1). So
    the break even point is where R * (m - 1) = R * Pi, or where m = Pi + 1.

    Sylvia.
     
  5. Tim Little

    Tim Little Guest

    No, the rabbit can do better than swimming in a straight line toward
    the closest point on shore.

    For example, suppose the shore were straight instead of circular, with
    the agent starting distance pi from the closest point, while the
    rabbit is at distance pi/m. If the rabbit swims in a straight line,
    they will reach that point at exactly the same time.

    If the rabbit swims at angle A, then the agent must run extra distance
    (pi/m) tan A, while the rabbit must swim an extra (pi/m) (sec A - 1).
    The rabbit is better off if tan A > m (sec A - 1), which has solutions
    in A for any m. So for a straight shore, the rabbit is always better
    off swimming at some nonzero angle.

    The circular shore does change the distances, but the same pattern
    holds: the rabbit is always better off swimming at an angle, even if a
    small one.


    - Tim
     
  6. Dave

    Dave Guest

    I solved this when it appeared in rec.puzzles in 1992 (using a duck
    and a fox).

    See http://groups.google.com/group/rec.puzzles/msg/050273ed70e4a9f6

    The bottom line is that there is a strategy by which the rabbit can
    escape as long as the agent can run no more than v =
    4.6033388487517003525565820291030165130674... times as fast as the
    rabbit can swim. The number v is the reciprocal of the solution of the
    transcendental equation sqrt(1-r*r) = r*(pi+arccos(r)), which can be
    derived using trigonometry.

    Dave
     
  7. M Rath

    M Rath Guest

    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 ?

    Okay the radius of the pond is 1 so the rabbit must swim 1 . The pond
    circumference is Pi*radius*2 but the agent must run only half the
    circumference for a distance of Pi . Then rabbit can swim at a rate of 1 so
    the agent can run at a rate of 4.

    Rate * Time = Distance
    &
    Time = Distance / Rate

    So the rabbit can swim to the shore in

    Time = 1 / 1 or 1 .

    And the agent can run to the opposite shore in

    Time = Pi / 4 or 0.785 .

    And so I seem to have the wrong answer. But the second part of the problem
    based on my answer would be

    Pi / Rate = 1
    Rate = 3.14

    If the agent runs only 3.14 times as fast as the rabbit then they time...and
    a tie goes to the base runner.
     
  8. M Rath

    M Rath Guest

    So the rabbit swims an arc. The agent is running a counterclockwise circular
    curve while the rabbit is swimming a counterclockwise...outward spiral.
     
  9. M Rath

    M Rath Guest

    See...in the extreme...at each instantaneous moment of the agents movement
    the rabbit makes a new line from the agent to the rabbit to the shore.
     
  10. Androcles

    Androcles Guest

    Where I live we shoot rabbits and outgrabe mome raths.
     
  11. Dave

    Dave Guest

    No. The rabbit wants to swim in a straight line. It is the shortest
    distance from where he is to a point on the shore. If he swims in an
    arc, it will take longer than on a line, meaning that the agent has
    more time to reach him.

    Dave
     
  12. M Rath

    M Rath Guest

    M Rath wrote:

    "> > The rabbit is in the middle of a circular pond. The agent is on the
    edge
    Dave wrote:

    No. The rabbit wants to swim in a straight line. It is the shortest
    distance from where he is to a point on the shore. If he swims in an
    arc, it will take longer than on a line, meaning that the agent has
    more time to reach him.

    M Rath wrote:

    If the rabbit swims ONE straight line to the shore...then the agent is
    waiting for him.

    And the solution hereabouts says that the rabbit keeps turning away from the
    agent until a point where he can break for shore. But how does the rabbit
    know when he can break for shore ?

    I'm saying that with each movement of the agent...the rabbit turns away from
    the agent. So the rabbit swims an outward spiral that does prove that the
    rabbit can get away. See...the rabbit stays in the water until the point
    when he touches shore with the agent some distance away...
     
  13. Tim Williams

    Tim Williams Guest

    Seems clear to me. If the rabbit travels in a straight line,
    regardless of which direction is taken, that line is always a radius.
    Therefore, the point on the shore closest to the agent (without
    reaching the agent) is just four radii of circumference (that is, 4
    radians angle) from where he was standing.

    However, the agent can reach the other side of the pond sooner than
    3.14 radii, that is, the optimal point exactly opposite the agent. So
    a straight-line solution is very easy: the ratio of speeds is pi, and
    the rabbit cannot escape.

    But that would be too easy, wouldn't it? If the rabbit is allowed a
    curved path, then I would believe some of these complicated solutions
    (a trancendental equation, eh?).

    Tim
     
  14. Nobody

    Nobody Guest

    If the rabbit swims in a straight line from the centre, the agent can beat
    him to the shore. So he must get closer to the shore while remaining
    diametrically opposite the agent.

    So long as the rabbit is less than r/4 from the centre, he can maintain
    diametric opposition. If the agent runs clockwise, the rabbit swims
    anti-clockwise and vice-versa. The rabbit moves at 1/4 of the speed,
    but is at less than 1/4 the radius, so his maximum angular speed is
    higher than the agent's. He only needs to match the angular speed,
    so whatever speed is left over can be used for outward motion.

    Once he reaches r/4 from the center, the rabbit can maintain diametric
    opposition, but not while moving outward. But at this point, he is only
    3r/4 from the closest point on the shore, while the agent is pi*r from
    that point. So he can head in a straight line to the shore and get there
    before the agent does.
     
  15. riverman

    riverman Guest

    Only if the agent stands still until the last possible moment. I think
    the agent will move continuously, and as soon as the rabbit starts
    moving in any direction, the agent will move toward the point that is
    the closest to the rabbit at that moment. Let's call the agent 'Xeno'.
     
  16. Sylvia Else

    Sylvia Else Guest

    No - until the rabbit is 1/4 of the radius away from the centre, he can
    swim fast enough, in a suitable direction, to keep the agent exactly
    opposite. So it doesn't matter if the agent moves.

    Sylvia.
     
  17. Nick

    Nick Guest

    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.
     
  18. Nobody

    Nobody Guest

    Simple algebra is sufficient to determine that the agent's speed needs
    to be at least pi+1 times the rabbit's speed.

    If the radius is r, the agent's speed is a and the rabbit's speed is b:

    #1. The rabbit can remain diametrically opposed to the agent up
    to a distance of r*b/a from the centre, i.e. r-r*b/a = r*(1-b/a) from the
    shore.

    #2. From there, the time it takes for the rabbit to reach the closest
    point on the shore is r*(1-b/a)/b = r*(1/b-1/a).

    #3. The time it takes the agent to reach that point is pi*r/a.

    #4. They will draw when the times in #2 and #3 are equal, i.e.

    r*(1/b-1/a) = pi*r/a
    => 1/b-1/a = pi/a
    => a/b-1 = pi
    => a/b = pi+1

    If the ratio is greater than pi+1, the rabbit can't win using this
    strategy. But proving that this strategy is optimal (i.e. it can't win
    using another strategy) may be rather more involved.
     
  19. Guest

    I'd hate to tackle it analytically. But numerically, it seems
    perfectly tractable.

    Assume that the rabbit isn't going for style points (swimming the
    backstroke in circles to taunt the agent) and is going for the maximum
    "lead" at the point where he exits the water.

    Assume that the rabbit has reached his 1/4 r "jumping off" point. The
    rabbit will initially head straight for shore. But only long enough
    for the agent to pick a chase direction.

    Once the agent has picked a direction, the rabbit chooses a new
    straight line course. This course can be chosen by differentiation --
    how much additional distance must the agent run versus how much
    additional distance must the rabbit swim as a function of an
    incremental change in course angle.

    If agent running distance is a and rabbit swimming distance is h and
    the rabbits selected swimming angle is theta then the hare is trying
    maximize

    a/4 - h

    so he needs to solve:

    d(a)/4 - d(h) / d(theta) = 0


    The rabbit may continue making this calculation as it approaches the
    shore. The result will remain unchanged as long as the agent does not
    turn around. The selected angle only depends on the angle made
    between the
    shoreline and the rabbit's course line at the point where they
    intersect. This means that the rabbit will swim a straight line
    course.

    If one is trying to zero in on the optimal value for the agent's
    speed, one can can adjust the agent/rabbit speed ratio and until the
    critical value is found.
     
  20. Tim Williams

    Tim Williams Guest

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

    Tim
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-