ark@rabbit.UUCP (Andrew Koenig) (02/16/84)
A woman is in a rowboat in a circular lake. On the shore is a man with an axe, out to kill her. He can run four times as fast as she can row, and starts at the point on shore nearest her initial position. If she can reach any point on shore before he does, she can outrun him and escape. Is there a strategy that will ensure her survival? Assume that both people know both of their positions accurately at all time, that the shore is unobstructed all around the lake, that either of them can reverse direction instantly, and that it takes no time for the woman to get out of the boat and start running.
stevev@tekchips.UUCP (Steve Vegdahl) (02/18/84)
> A woman is in a rowboat in a circular lake. On the shore is a man with > an axe, out to kill her. He can run four times as fast as she can row, > and starts at the point on shore nearest her initial position. If she > can reach any point on shore before he does, she can outrun him and escape. > > Is there a strategy that will ensure her survival? Assume that both > people know both of their positions accurately at all time, that the > shore is unobstructed all around the lake, that either of them can > reverse direction instantly, and that it takes no time for the woman to > get out of the boat and start running. In addition to the trivial strategy of staying in the middle of the lake indefinitely, there is a way she can make it to shore safely. I will use polar coordinates in describing the solution, with the origin at the middle of the lake; the radius of the lake is assummed to be 1. (The axe-man's position will always be of the form (1, theta), as it does not make much sense for him to be away from shore.) Step 1. The woman should get herself in position (-0.25, theta), where the axe-man is at (1, theta). She can get herself within epsillon of this point by racing around the circle in the center of the lake whose radius is 0.25; as long as she is within this circle, she can change her "theta" faster than the axe-man can change his. Step 2. Race to the point (-1, theta). She can get there in 3 (possibly plus epsillon) time units, as she is 0.75 away, and she travels at a speed of 0.25. It will take the axe-man 3.14+ (i.e. pi) time units to get there.