Escape the bear in the circle?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

mathocean149
Posts: 2
Joined: Fri Dec 25, 2015 8:13 am UTC

Escape the bear in the circle?

Postby mathocean149 » Fri Dec 25, 2015 8:19 am UTC

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.

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: Escape the bear in the circle?

Postby emlightened » Fri Dec 25, 2015 11:23 am UTC

Spoiler:
Depends on the sum of the radii of the protagonist and bear. If 0, then, as far as I know, the bear can get arbitrarily close to the protagonist but may never touch them. If positive, then the bear will always catch the protagonist, simply by always moving directly towards them. Another option is for the bear to move to the middle, and then always stay on the same radius as the protagonist, but otherwise move gradually closer.

The bear won't nab me, though. I'm not the protagonist. :wink:

"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."

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Escape the bear in the circle?

Postby Cradarc » Fri Dec 25, 2015 7:02 pm UTC

Spoiler:
Bear always wins.

Suppose at time T = 0, bear is located at the origin and person is at (1,0). Coordinate system is arbitrary. Consider the possible positions at time T = t, where t is infinitesimally larger than 0.
If v = velocity of the person, let r = v/t. So at T = t, the person can be located anywhere on the circle: (x-1)2 + y2 = r2
Since the bear moves at the same velocity as the person. It can be located anywhere on the circle: x2 + y2 = r2

We are assuming both parties have 0 reaction time and can change direction instantaneously. This means the bear can pick the optimal location to minimize its distance to the person, regardless which direction the person decides to go. Suppose the person decides to go in a direction that forms the angle k with the positive x axis (counterclockwise). At time T = t, the person is located at (1+rcos[k], rsin[k]). The bear will pick an optimal angle m to end up in the location (rcos[m],rsin[m]).

m must be chosen to minimize the distance. So the bear must minimize:
(1+r(cos[k]-cos[m]))2 + (r(sin[k]-sin[m]))2 = 1 + 2r(cos[k]-cos[m]) + r2((cos[k]-cos[m])2 + (sin[k]-sin[m])2)
= 1 + 2r(cos[k]-cos[m]) + 2r2(1 - sin[k]sin[m] - cos[k]cos[m])
= 1 + 2r(cos[k]-cos[m] + r(1 - sin[k]sin[m] - cos[k]cos[m]))

For the bear to win:
cos[k]-cos[m] + r(1 - sin[k]sin[m] - cos[k]cos[m]) < 0
cos[k] < cos[m] + r(cos[m-k]-1)

If we take the limit as r -> 0, we see that the bear simply has to pick m so that cos[k] < cos[m]. This is always possible unless k = multiple of 2pi, when the person is moving directly away from the bear. In that case, the person can only maintain the same distance from the bear, never increasing it.
Because of the circular boundary the person cannot move directly away from the bear indefinitely. So the bear must eventually catch up.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
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?

Postby Vytron » Fri Dec 25, 2015 8:45 pm UTC

Spoiler:
emlightened wrote:Depends on the sum of the radii of the protagonist and bear. If 0, then, as far as I know, the bear can get arbitrarily close to the protagonist but may never touch them.


I think that Cradarc shows that there's a time in the future at which the bear and the protagonist are exactly at the same point, and that the protagonist can only delay this as much as possible, but at that point the bear nabs them.

The chase looks a bit boring, though. The best case scenario is to maximize their distance, like, put the protagonist at the very top of the circle and the bear at the very bottom. The bear moves in the up direction towards the protagonist, but the protagonist doesn't move! This is because any movement would make it closer to the bear, so the best running away strategy is to not move.

Any other position where the protagonist starts only makes them want to reach the boundary furthest away from the bear ASAP, and then they stay there, resigned. It never looks quite like this :(

emlightened wrote:The bear won't nab me, though. I'm not the protagonist. :wink:


Nice, I only hope this was the intended solution :mrgreen:


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?

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Escape the bear in the circle?

Postby notzeb » Sat Dec 26, 2015 9:49 am UTC

Hehehehehehe
Spoiler:
It's a famous puzzle. A quick google search turns up this (hey, it's faster than explaining the solution myself!). Alternate explanations found via google: this, this, and this.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Escape the bear in the circle?

Postby Cradarc » Sat Dec 26, 2015 8:11 pm UTC

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:
Their solution assumes that there is always a smaller epsilon to move that guarantees the beast won't catch up. But you can literally say that about any race scenario and it totally contradicts the uniformity of space. Consider this example:

The lion is at origin and the person is 1 unit away. They are running on a single lane, straight road. In the time the lion runs 1/2 units, the person runs 1/4 units. In the time the lion runs another 1/3 units, the person runs 1/5 units, etc.
Let H[n] = finite sum of harmonic series up to nth term.
After n steps, the person is located at H[n+3]-1/2-1/3 = H[n+3] - 5/6 from the origin.
After n steps, the lion is located at H[n+1]-1 from the origin.
H[n+1]-1 < H[n+3] -5/6
H[n+1] < H[n+3] + 1/6
Clearly, there is no step at which the lion can catch up to the human.

At the nth step, the lion moves 1/(n+1) units in the same time that the person moves 1/(n+3) units. Rate = distance/time, so clearly the person moves slower than the lion at every step.
Now consider the total distance the human has to run. The harmonic series doesn't converge, which means the total distance is infinite, so the steps cannot be completed in a finite amount of time.

Thus, the person can maintain a speed slower than the lion at all times, yet still evade the lion indefinitely on a straight path. QED? Yeah...no. It's called common sense.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
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?

Postby Vytron » Sat Dec 26, 2015 9:30 pm UTC

Spoiler:
notzeb wrote: It's a famous puzzle. A quick google search turns up this (hey, it's faster than explaining the solution myself!). Alternate explanations found via google: this, this, and this.


I don't think that really woks.

As it says, the bear is very intelligent, so if the bear can predict that you'll use that strategy, all it needs to do is going to a point where it knows you'll eventually be, and wait for you. Their mistake is assuming the bear would chase you forever, but if I was the bear, I could catch you.

User avatar
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?

Postby Vytron » Sat Dec 26, 2015 11:00 pm UTC

New "solution":
Spoiler:
Heh, this just struck me:

Since the bear's velocity is always the same as the man's velocity, the bear's velocity is limited by the way the man moves. That is, the bear can never move faster than the man.

So, all the man needs to do is setting their speed to 0, and the bear will not be able to chase it at all (since that'd mean the bear would have a higher speed than the man) :P

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Escape the bear in the circle?

Postby jaap » Sun Dec 27, 2015 9:02 am UTC

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.

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: Escape the bear in the circle?

Postby emlightened » Sun Dec 27, 2015 3:41 pm UTC

Spoiler:
Vytron wrote:The chase looks a bit boring, though. The best case scenario is to maximize their distance, like, put the protagonist at the very top of the circle and the bear at the very bottom. The bear moves in the up direction towards the protagonist, but the protagonist doesn't move! This is because any movement would make it closer to the bear, so the best running away strategy is to not move.

Only while the bear is less than halfway there. If the bear is at the origin, then moving around the edge of the circle has no change in distance, and moving around the edge when the bear is any closer actually gets them further away. Still, If I was stuck in a circular cage, and had a bear running at full speed towards me, I'd probably not move due to fear. :P

Cradarc wrote:Thus, the person can maintain a speed slower than the lion at all times, yet still evade the lion indefinitely on a straight path. QED? Yeah...no. It's called common sense.
It's possible, in the sense that if the lion is moving as speed 1, and you're moving at speed 0.9 at t=0, 0.99 at t=1, 0.999 at t=2, etc., (with distances 0.9, 1.89, 2.889 at t=1, t=2 and t=3; this doesn't drop below t-(1/9)) then you're still always moving slower; just negligibly so after a couple of seconds. All the paper does is use a different, slower to converge series. And, of course, a circle isn't a straight road.

"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."

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Escape the bear in the circle?

Postby Cradarc » Sun Dec 27, 2015 7:17 pm UTC

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.

flewk
Posts: 12
Joined: Fri Dec 25, 2015 12:47 pm UTC

Re: Escape the bear in the circle?

Postby flewk » Mon Dec 28, 2015 9:49 am UTC

Spoiler:
It seems like you are saying the bear is smarter than the protagonist? If so, then the bear should always win as long as it is a finite space. If the bear is forced to follow some specific algorithm, then a "smart" protagonist should be able to avoid it indefinitely.


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.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Escape the bear in the circle?

Postby Cradarc » Mon Dec 28, 2015 9:28 pm UTC

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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Escape the bear in the circle?

Postby jaap » Tue Dec 29, 2015 12:14 am UTC

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:
Let r be the persons radius, v his velocity. Suppose the bear is on the person's radius, at a distance d from the person.
The bear is then at radius r-d.
The bear's tangential velocity component is v*(r-d)/r
The bear's radial velocity component is then sqrt(v^2 - [v*(r-d)/r]^2 )
Therefore d'(t) = -sqrt(v^2 - [v*(r-d)/r]^2 ).
According to Wolfram Alpha, this differential equation has the solution
d(t) = 2r* tan^2 (c-vt/2r) / [ 1+ tan^2 (c-vt/2r) ]
for some c which depends on the boundary condition.
This distance d becomes zero when t is such that c-vt/2r = 0 and those tans become zero.
According to the paper linked earlier, the person can essentially follow an outward spiral that converges to some maximal radius, and apparently the expansion can be chosen such that it stays just ahead of the bear, but I'm yet to convince myself of this.

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: Escape the bear in the circle?

Postby emlightened » Tue Dec 29, 2015 2:24 am UTC

flewk wrote:
Spoiler:
It seems like you are saying the bear is smarter than the protagonist? If so, then the bear should always win as long as it is a finite space. If the bear is forced to follow some specific algorithm, then a "smart" protagonist should be able to avoid it indefinitely.

Spoiler:
No, because there is always an optimum algorithm that a "smart" bear/person would do, and that could be the specific algorithm in question.

Partial mathematical solution:
Spoiler:
The distance between the person and the bear cannot increase; this is a basic principle that a 'smart' bear would follow (at least in concave shapes on the Euclidian plane).
For simplicity's sake, call the radius of the circle 1, the speed of the human and bear 1, and adjust the speed/time units to match.
The bear chooses to always stay on the same radius as the person, and otherwise moves directly towards them.
It is not advantageous for the person to move towards the bear, so the angle that they move relative to the bear is always between 90° and 180° (as there is no advantage for moving counterclockwise over clockwise/vice-versa, they may as well only move in one of the directions).
The person cannot move outwards indefinitely, and so must always come within ε1 of some radius r, for any positive ε and some unique r≤1. (so, eventually, r-ε1<pperson≤r≤1, for any ε1>0 and some r≤1)
The outwards speed the bear moves, v, is √(1-(pbear/pperson)2).
√(1-(pbear/pperson)2) > √(1-(pbear/(r-ε1))2)
We can put this into the differential equation d(pbear)/dt = √(1-(pbear/(r-ε1))2) (with a bear going slightly slower than they can).
Now, if limt→∞(pbear) = r-ε1, then, for any ε2>0 and some t (as a function of r, ε1 and ε2), r>pbear>r-ε12, and as r-ε1<pperson≤r, we have pperson-pbear12, for any ε1 and ε2, and all sufficiently large t.

Therefore, if limt→∞(k)=v, given that dk/dt = √(1-(k/v)2) (we've replaced pbear with k and r-ε1 with v), the bear can get arbitrarily close to the person.

I'm pretty sure that that's the case (it's an increasing function, and bounded with dk/dt=0 for k=v, so what else can it be?) but I haven't proved it. I also haven't proved that it's impossible for the bear to catch the person for any method the bear uses, but this is halfway there.


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 t-d/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."

User avatar
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?

Postby Vytron » Thu Dec 31, 2015 7:51 am UTC

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.

mward
Posts: 123
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Escape the bear in the circle?

Postby mward » Mon Jan 04, 2016 1:15 pm UTC

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

User avatar
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?

Postby Vytron » Thu Jan 07, 2016 6:24 am UTC

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.

User avatar
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?

Postby jestingrabbit » Thu Jan 07, 2016 3:21 pm UTC

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.

User avatar
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?

Postby Vytron » Thu Jan 07, 2016 9:37 pm UTC

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:

Image

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):

Image

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:

Image

And once they do that, we have these new initial conditions:

Image

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:

Image

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 :roll:

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

Image

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:

Image

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

Image

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:

Image

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:
man999.png
man999.png (4.77 KiB) Viewed 5137 times
man998.png
man998.png (5.63 KiB) Viewed 5137 times
maN997.png
maN997.png (10.57 KiB) Viewed 5137 times
man996.png
man996.png (4.83 KiB) Viewed 5137 times
man995.png
man995.png (9.9 KiB) Viewed 5137 times
man994.png
man994.png (13.4 KiB) Viewed 5137 times
man993.png
man993.png (14.74 KiB) Viewed 5137 times
man992.png
man992.png (13.6 KiB) Viewed 5137 times
man991.png
man991.png (13.89 KiB) Viewed 5137 times


Disclaimer: The bear's name is Lion.

User avatar
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?

Postby jestingrabbit » Thu Jan 07, 2016 11:10 pm UTC

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.

flewk
Posts: 12
Joined: Fri Dec 25, 2015 12:47 pm UTC

Re: Escape the bear in the circle?

Postby flewk » Fri Jan 08, 2016 8:47 am UTC

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.

User avatar
Carmeister
Posts: 24
Joined: Fri Jan 24, 2014 5:10 am UTC

Re: Escape the bear in the circle?

Postby Carmeister » Wed Jan 13, 2016 10:26 pm UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 13 guests