Escape the bear in the circle?
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 2
 Joined: Fri Dec 25, 2015 8:13 am UTC
Escape the bear in the circle?
Our protagonist is stuck in a disk of radius R, together with a very intelligent bear who wants to eat them. The protagonist and the bear can move at the same exact speed, never get tired, and can change directions instantaneously. Will the bear eventually nab you, or can you forever escape it?
Last edited by mathocean149 on Fri Dec 25, 2015 7:49 pm UTC, edited 1 time in total.
 emlightened
 Posts: 42
 Joined: Sat Sep 26, 2015 9:35 pm UTC
 Location: Somewhere cosy.
Re: Escape the bear in the circle?
Spoiler:
██████████████████████████████████████████████████████████████████████████████████████████████████████
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
Re: Escape the bear in the circle?
Spoiler:
This is a block of text that can be added to posts you make. There is a 300 character limit.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
Spoiler:
I wonder about an interesting variation:
What if the protagonist can run away at velocity n+k where n is the bear's speed and k is not zero?
Re: Escape the bear in the circle?
Hehehehehehe
Spoiler:
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
Re: Escape the bear in the circle?
The explanations Notzeb linked to are suspiciously like the Zeno's paradox. At every step, the lion/bear gets closer to the person, yet it never fully overlap the person. The engineer inside me is grinding his teeth at that. I say we throw those mathematicians into the ring and see if they can pull it off.
Spoiler:
This is a block of text that can be added to posts you make. There is a 300 character limit.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
Spoiler:
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
New "solution":
Spoiler:
Re: Escape the bear in the circle?
Cradarc wrote:The explanations Notzeb linked to are suspiciously like the Zeno's paradox. At every step, the lion/bear gets closer to the person, yet it never fully overlap the person.
Basically, the bear can get arbitrarily close, but never actually reach its prey. I agree that the proof in that paper there is not terribly convincing, as it discretizes the continuous problem.
Try it out here:
http://www.jaapsch.net/bearcircle.htm
The larger circle is the bear, and you control it with your mouse  it always moves towards your mouse pointer at its maximum speed.
The strategy for the prey is to move around in a circle, always going in the direction away from the bear (that is, consider the radial line through the circle centre and the prey which splits the plane into two halves, and the prey moves in the direction of the half not containing the bear). The problem for the bear is that he has to approach the prey from the inside (anything else and the prey turns around and increases the distance). This leads to an expanding spiral path, and the closer he gets, the smaller the radial component of his velocity, so the slower the distance between them diminishes. This pushes the moment he would exactly reach the prey to infinitely far into the future, though he can get arbitrarily close.
 emlightened
 Posts: 42
 Joined: Sat Sep 26, 2015 9:35 pm UTC
 Location: Somewhere cosy.
Re: Escape the bear in the circle?
Spoiler:
██████████████████████████████████████████████████████████████████████████████████████████████████████
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
Re: Escape the bear in the circle?
jaap wrote:The strategy for the prey is to move around in a circle, always going in the direction away from the bear (that is, consider the radial line through the circle centre and the prey which splits the plane into two halves, and the prey moves in the direction of the half not containing the bear). The problem for the bear is that he has to approach the prey from the inside (anything else and the prey turns around and increases the distance). This leads to an expanding spiral path, and the closer he gets, the smaller the radial component of his velocity, so the slower the distance between them diminishes. This pushes the moment he would exactly reach the prey to infinitely far into the future, though he can get arbitrarily close.
I see. That makes more sense now. In order to reach the same "orbit", the bear must sacrifice some angular velocity. The person just has to move in a way that capitalize on that loss.
This is a block of text that can be added to posts you make. There is a 300 character limit.
Re: Escape the bear in the circle?
Spoiler:
jaap wrote:The strategy for the prey is to move around in a circle, always going in the direction away from the bear (that is, consider the radial line through the circle center and the prey which splits the plane into two halves, and the prey moves in the direction of the half not containing the bear). The problem for the bear is that he has to approach the prey from the inside (anything else and the prey turns around and increases the distance). This leads to an expanding spiral path, and the closer he gets, the smaller the radial component of his velocity, so the slower the distance between them diminishes. This pushes the moment he would exactly reach the prey to infinitely far into the future, though he can get arbitrarily close.
It doesn't push it infinitely far as the person is limited by the disk. Too lazy to calculate the exact time in terms of R and initial positions, but I was able to encircle(heh) the prey with my bear circle in less than a minute. This is because your strategy would push the person closer and closer to the boundary. Even while moving in a circle, the bear can position itself to force the tangential direction of the prey's circular path to move towards the boundary. As long as his foci of rotation is being pushed by the bear, he will get caught. Once the prey is at the boundary, the instant tangential velocity is no longer possible and the bear just inches closer and closer with the prey constantly trying to change directions.
Re: Escape the bear in the circle?
flewk wrote:This is because your strategy would push the person closer and closer to the boundary. Even while moving in a circle, the bear can position itself to force the tangential direction of the prey's circular path to move towards the boundary.
The tangential direction of the person's path, by definition, cannot point towards the boundary. Tangential means perpendicular to the radius. You have to have a component of velocity parallel to the radius to move towards the boundary.
How I understand the solution is that the person always moves on a circle concentric with the arena circle. The bear initially starts on another concentric circle of a different radius. In order for the bear to reach the person, it must expand its circle to have the same radius as the person while ending up at the same angle as well.
In the best case scenario for the bear, it starts at the perfect angle, but at a different radius. The claim is the bear cannot maintain the perfect angle if it wants to expand its radius. This is because as the bear's radius approaches the person's radius, the tangential velocity of the bear must approach the tangential velocity of the person. This reduces the rate at which the bear can expand its radius. Presumably, the mathematics work out such that the decrease in rate is large enough that the bear cannot converge to the the person's radius in finite time without destroying the matched angle property.
This is a block of text that can be added to posts you make. There is a 300 character limit.
Re: Escape the bear in the circle?
Cradarc wrote:flewk wrote:This is because your strategy would push the person closer and closer to the boundary. Even while moving in a circle, the bear can position itself to force the tangential direction of the prey's circular path to move towards the boundary.
The tangential direction of the person's path, by definition, cannot point towards the boundary. Tangential means perpendicular to the radius. You have to have a component of velocity parallel to the radius to move towards the boundary.
How I understand the solution is that the person always moves on a circle concentric with the arena circle. The bear initially starts on another concentric circle of a different radius. In order for the bear to reach the person, it must expand its circle to have the same radius as the person while ending up at the same angle as well.
In the best case scenario for the bear, it starts at the perfect angle, but at a different radius. The claim is the bear cannot maintain the perfect angle if it wants to expand its radius. This is because as the bear's radius approaches the person's radius, the tangential velocity of the bear must approach the tangential velocity of the person. This reduces the rate at which the bear can expand its radius. Presumably, the mathematics work out such that the decrease in rate is large enough that the bear cannot converge to the the person's radius in finite time without destroying the matched angle property.
Exactly, but I have run through the algebra now, and I think I was wrong. When the person does a circular orbit, the bear can close the distance in a finite time. It seems that the person does need to expand his radius to evade the bear.
Spoiler:
 emlightened
 Posts: 42
 Joined: Sat Sep 26, 2015 9:35 pm UTC
 Location: Somewhere cosy.
Re: Escape the bear in the circle?
flewk wrote:Spoiler:
Spoiler:
Partial mathematical solution:
Spoiler:
Now here's an interesting question: what if information doesn't travel instantaneously, but instead at a fixed speed? i.e. at time t, the bear and person only know where the other one was at time td/c (where d is the distance between them and c is the speed of information/light). Assume c is arbitrary, but greater than their speeds.
Also, note that as the bear gets closer to catching the person, they get progressively quicker reaction times, so it is possible to catch the person (at least if the person's reaction times are slower, not equal).
██████████████████████████████████████████████████████████████████████████████████████████████████████
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
jaap wrote:
Try it out here:
http://www.jaapsch.net/bearcircle.htm
The larger circle is the bear, and you control it with your mouse  it always moves towards your mouse pointer at its maximum speed.
No, it doesn't.
At least not "continuously". The bear is drawing a line to where my mouse is, and then there's a segment of time in which it follows the line. The bear should stop following this line and following my mouse as soon as I move it, but it doesn't do that.
So try this:
For a time segment, those that appear on the paper, where the bear will move from point A to point B, cut that time segment in half, and allow the bear to change direction again at the half point. You'll see when it reaches the new B, it'll be closer to the protagonist.
Do it again. Cut the A to B segment in 4, you'll have 3 points at which the bear can change directions. It'll be even closer to the everyman.
Repeat this infinitely, so that the distance the bear can travel isn't quantized, but analog, and now the protagonist can't escape.
And it doesn't really make sense to talk about these segments of time, check this variation:
The bear can travel some distance in one minute, but can't change directions after deciding where will it go. The man can do the same.
The bear chooses point B and moves to it, so does the man. There's always a point at which the man can move to avoid being caught.
Okay, fine. Now:
The bear can travel some distance in 30 seconds, but can't change directions after deciding where will it go. The man can do the same.
The bear chooses point B and moves to it, so does the man. There's always a point at which the man can move to avoid being caught.
And then...
The bear can travel some distance in 15 seconds, but can't change directions after deciding where will it go. The man can do the same.
The bear chooses point B and moves to it, so does the man. There's always a point at which the man can move to avoid being caught.
Etcetera.
How does it look like if we zoom in on the protagonist and the bear as the time segments are cut in half?
Well, the man and the bear, being points, look the same, but their distances have doubled, as has the arena. Now the man has double the space to escape the bear, it's no surprise that the bear doesn't catch up, as it's like the variation with an infinite arena.
I'll claim that this bizarre variation where the bear decides where to go and can't switch directions while going there is equivalent to the solution presented in the OP, so that if the time segments were kept the same instead of being lowered, it'd be as if the arena doubled its size at every time segment.
How can a scenario where the arena is finite behave the same as one where the arena doubles its size at every time segment?
So my claim is that the solution as presented in the paper doesn't follow the "infinite strength" that the bear should have.
If the bear has an optimal path to follow from Point A to Point B, but when you truncate the path in half and allow the bear to change direction halfway it'd go to a different B, it means the original path wasn't optimal. If you already had decided for the optimal strategy for the man and then it'd change after knowing the new B of the bear, halfway in the time segment, then it wasn't optimal to begin with.
So the problem here is digitizing the analog, and if the page you linked to could follow my mouse with infinite accuracy (that the bear should have, with its infinite strength) I'd catch the man.
It seems the problem the paper is solving only works for an arbitrarily strong bear, but not an infinitely strong bear, as it's being forced to follow some path on a line segment even though it should be able to change directions an infinite number of times in the segment.
Re: Escape the bear in the circle?
When using the winning strategy, the protagonist is following a path on a line segment (with the segments getting shorter each time). Given this fact, the bear can follow any path, but cannot do any better than move directly towards the end point of the protagonist's current line segment. This is the "worst case" (for the protagonist): but with a careful choice of line segments the progatonist can always keep away from the bear.Vytron wrote:It seems the problem the paper is solving only works for an arbitrarily strong bear, but not an infinitely strong bear, as it's being forced to follow some path on a line segment even though it should be able to change directions an infinite number of times in the segment.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
mward wrote:Given this fact, the bear can follow any path, but cannot do any better than move directly towards the end point of the protagonist's current line segment.
But we know the bear will not catch the protagonist if it moves there.
Allow the bear to, halfway on the segment, look up a new location of the protagonist, and change direction there, and, since the other strategy gets arbitrarily close, this one does catch it.
Example:
Protagonist will move to location x in one second.
Bear knows this, so Bear starts moving towards location x.
Half a second later, bear checks where will the protagonist be one second later.
We know the protagonist always moves, so the protagonist would have moved to x in half a second, and to some new location at another half second. Call this second location y.
Let the bear change directions, and move towards y instead of towards x.
At one second after the chase starts, the bear that changed directions will be more close to the protagonist than one that only moved towards x. This shows that moving towards x wasn't optimal.
Now, this strategy isn't enough and the bear can only get abritrarily close, but now it can get arbitrarily closer. So, just split a second into infinite segments so that the bear changes direction towards where the Protagonist will be infinite times (allowed by infinite strength), and it'll get infinitely closer to the protagonist, catching it.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Escape the bear in the circle?
Vytron wrote:mward wrote:Given this fact, the bear can follow any path, but cannot do any better than move directly towards the end point of the protagonist's current line segment.
But we know the bear will not catch the protagonist if it moves there.
Allow the bear to, halfway on the segment, look up a new location of the protagonist, and change direction there, and, since the other strategy gets arbitrarily close, this one does catch it.
But at the end of that straight path by the man, the bear is further away than it would be if it traveled straight towards the endpoint. So the gap at the end of that part of the mans strategy is bigger than if the bear went straight at the destination.
I agree that the explanations aren't great atm. If I get the time I'll lay out a proper mathematical proof, with proper limits, that properly proves what's going on.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: Escape the bear in the circle?
jestingrabbit wrote:But at the end of that straight path by the man, the bear is further away than it would be if it traveled straight towards the endpoint. So the gap at the end of that part of the mans strategy is bigger than if the bear went straight at the destination.
The destination x (to where the man was moving at the start, where it arrived at "Second 1"), not the destination y (where it moves to after arriving at destination x, at "Second 1.5".)
Actually, let me show the graphics.
Initial conditions:
From this position, the man does some calculations and, depending from the distance of the bear, and the angle it produces relative to the center of the circle (etc.) finds a spot that is "safe". This point appears as blue here (x):
This spot is safe, because if we drew a circle with an orange outline that covers all the points at which the man can be at the end of the time segment, and do the same with the bear, this spot is outside of the bear's circle, and as close to the center as possible. Here, the bear at the end of the segment, moving towards x, ends arrives at the green spot:
And once they do that, we have these new initial conditions:
That are no different from the other one, the man can find a new x and move there, and the bear will not catch the man in this time segment either:
And so on and so forth. The bear never catches the man.
My answer to this? What a dumb bear!
No, the bear is not chasing the man optimally, because if we know this strategy never catches the man, the bear might as well stay still
A better strategy is for the bear to cut the time segment in half, and looking up where will the man be at the second x, that we call y...
So here's what the bear sees halfway through the initial segment (the bear's current position in yellow, and the man's current position in magenta). Do you see how it sees that it'll make one straight turn one way, and then another? I'll highlight it in...Cyan. Man, I run out of colors fast:
Yeah, what it said. How can a bear with an optimal strategy and infinite strength waste time with such moves?
The bear switches direction and goes on a straighter path, in a blue line...
It'll end much closer to the man.
But, if 1/4 of the distance the bear knows this, it would see that that path isn't optimal either (now in cyan), and move towards y earlier:
This is even closer to the man.
So if the bear does this an infinite number of times, at every point in the circle, it'll caught the man.
This was clear in the applet where the bear followed the mouse in the chase, but it didn't change directions to follow my mouse instantly, instead moving dumbly to where my mouse used to be on the last segment.
Props
Spoiler:
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Escape the bear in the circle?
But the man's second move depends on where the bear ends up. Recalculate the next target for the man based on the bears actual location in your scenario based on where the bear actually ends up when the man is at his first destination, see what happens.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Escape the bear in the circle?
Cradarc wrote:flewk wrote:This is because your strategy would push the person closer and closer to the boundary. Even while moving in a circle, the bear can position itself to force the tangential direction of the prey's circular path to move towards the boundary.
The tangential direction of the person's path, by definition, cannot point towards the boundary. Tangential means perpendicular to the radius. You have to have a component of velocity parallel to the radius to move towards the boundary.
How I understand the solution is that the person always moves on a circle concentric with the arena circle. The bear initially starts on another concentric circle of a different radius. In order for the bear to reach the person, it must expand its circle to have the same radius as the person while ending up at the same angle as well.
In the best case scenario for the bear, it starts at the perfect angle, but at a different radius. The claim is the bear cannot maintain the perfect angle if it wants to expand its radius. This is because as the bear's radius approaches the person's radius, the tangential velocity of the bear must approach the tangential velocity of the person. This reduces the rate at which the bear can expand its radius. Presumably, the mathematics work out such that the decrease in rate is large enough that the bear cannot converge to the the person's radius in finite time without destroying the matched angle property.
From what I understood of the other guy's suggestion, the person moves in a spiral away from the bear. The spiral's instantaneous velocity will point at the boundary at all times. They are enclosed.
 Carmeister
 Posts: 24
 Joined: Fri Jan 24, 2014 5:10 am UTC
Re: Escape the bear in the circle?
Here's an alternate way of thinking about it that preserves the continuity of the problem while avoiding the confusion of thinking about it in discrete steps:
Describe a function that, given the path the bear takes, returns a path the man can take that will allow him to evade the bear for all time. To ensure the fact that the man doesn't actually know ahead of time what the bear will do, this function must have the property that if two different input paths are identical for the first t seconds, then the two output paths it gives for those inputs must also agree for the first t seconds.
If you can find such a function, then the man can escape; if it is impossible to do so, then the bear will eventually be able to catch him.
It should work the other way around as well: find a function for the bear that, given the man's path, returns a path that will allow him to eventually catch the man. If it's possible, then the bear wins. If not, then the man wins.
Ideally, exactly one of those two functions should exist. Intuitively that seems obvious, but I don't see an easy way to prove it.
Describe a function that, given the path the bear takes, returns a path the man can take that will allow him to evade the bear for all time. To ensure the fact that the man doesn't actually know ahead of time what the bear will do, this function must have the property that if two different input paths are identical for the first t seconds, then the two output paths it gives for those inputs must also agree for the first t seconds.
If you can find such a function, then the man can escape; if it is impossible to do so, then the bear will eventually be able to catch him.
It should work the other way around as well: find a function for the bear that, given the man's path, returns a path that will allow him to eventually catch the man. If it's possible, then the bear wins. If not, then the man wins.
Ideally, exactly one of those two functions should exist. Intuitively that seems obvious, but I don't see an easy way to prove it.
Who is online
Users browsing this forum: No registered users and 13 guests