wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Heet seeking missiles
        
(Message started by: jollytall on Mar 17th, 2006, 1:05pm)
Title: Heet seeking missiles
Post by jollytall on Mar 17th, 2006, 1:05pm
I am sorry if this is a duplicate, but I looked through the list of all threads and tried to ask around, still could not find, while I think I have a solution.

The riddle was:
Four heat-seeking missiles are initially placed at the corners of a square with side length s. Each missile flies at a constant speed toward the missile on its left. Describe the path each missile takes until it collides with the rest in the square's center. What is this path's length?
Generalize to n missiles on a regular n-gon.

For N=4
The surprising result is that they never meet.
[hide]Let's assume that they meet following a certain path. It is clear that it cannot be straight to the center. If not, then we can measure the total angle the missile traveled around the center (Alpha>0). If during the path we check any single moment, it is identical with the initial state (the only difference is that they are closer to each other, but still form a square and travel towards the one on their left). If this point is an angle of Beta (>0) from the initial state, then the rest of the journey is Alpha-Beta. On the other hand, looking at the second state as a starting point, the remaining journey must be Alpha. It is a contradiction for any finite Alpha.[/hide]

Nevertheless the path can be described and it's length has a [hide]finite value[/hide].
The lenght is the easier:
[hide]If we look at an inifinitely small part of the journey, then we can easily see a isosceles triangle, where while it gets closer to the origo by x, it has to travel sqrt(2)*x (like a plane landing at an angle of 45 degree). Since the original distance to the origo is 1/sqrt(2), the total length of the path is 1.[/hide]
The path:
[hide]It is a sort of spiral, where after one whole round the distance to the origo reduces to a given fraction of the original distance. Looking again at the isosceles triange, for every infinitely small dAlpha, the original r distance to the origo changes by r*dAlpha (dr/dAlpha=r), i.e. the distance to the origo is an r=r0exp(Alpha) function of Alpha (choosing the Alpha direction so, that by travelling, Alpha goes to the negative direction). It means that by the time the missile turns 90 degree (the direction of the chased missile at the start) it is cca 80% closer to the origo than when it started. By the time it reaches the position of the third missile, it is already at cca 4% of the original distance and by the end of the first full round it is at 0.2%. So the missiles will be very dizzy soon.[/hide]

For N missiles it can be done a very similar way, choosing the scale so, that the initial distance of each missile to the origo is 1.
If I did not miscalculate, then the total length of the path is [hide]1/sin(pi/N)[/hide], while the path is [hide]r=exp(Alpha*tan(pi/N)).[/hide]
Title: Re: Heet seeking missiles
Post by Icarus on Mar 17th, 2006, 3:03pm

on 03/17/06 at 13:05:57, jollytall wrote:
Let's assume that they meet following a certain path. It is clear that it cannot be straight to the center. If not, then we can measure the total angle the missile traveled around the center (Alpha>0). If during the path we check any single moment, it is identical with the initial state (the only difference is that they are closer to each other, but still form a square and travel towards the one on their left). If this point is an angle of Beta (>0) from the initial state, then the rest of the journey is Alpha-Beta. On the other hand, looking at the second state as a starting point, the remaining journey must be Alpha. It is a contradiction for any finite Alpha.


I don't buy this argument. It is true that the angle would have to be infinite, but this is not impossible if the radius goes to zero.
Title: Re: Heet seeking missiles
Post by jollytall on Mar 18th, 2006, 12:24am
You are right Sir, the "they never meet" phrase was vague. Let me specify.

Since the length of the path is finite and the speed (assumed linear speed) of the missiles is constant, the missiles must meet after a finite time.
On the other hand the paths do not meet after any finite rounds they go around the origo. The quoted logic was to prove this.

It seems, it is again one of those where pure mathematics cannot give a clear description of a problem in physics, since the missiles are not points, they cannot have an infinite anglespeed, etc. One way to make the original riddle physically working, we can ask that there are four missiles each 1 meter long and inifinitely narrow (this latter shows that abstraction is not always impossible) in four corners of a square with sides s long. Etc.

A bit of a problem of Achilles and the Turtle (although there they graphically meet too) or whether the L(n)=0.999...999 sequence (one of the forum's favourites - btw. how do I add link?) with n 9-s reaches 1, especially if time is involved and we get from L(n-1) to L(n) in 1 second or in another version in 1-L(n) second.
Title: Re: Heet seeking missiles
Post by snow on May 21st, 2008, 9:21am

Quote:
The riddle was:
Four heat-seeking missiles are initially placed at the corners of a square with side length s. Each missile flies at a constant speed toward the missile on its left. Describe the path each missile takes until it collides with the rest in the square's center. What is this path's length?

I've long used this in MATLAB classes as an example of asking the right questions of differential equations.  I state this using dogs, and ask three questions:
1. Where do they meet,
2. When do they meet (equivalent to What distance have they traveled)
3. What direction are they facing.

1. Is easy by symmetry.
2. Becomes easy if you look from the point of view of one of the dogs, who at any instant sees another dog directly ahead and runs toward it at full speed (which we will assume is 1).  Since dogs start at distance s apart and end at distance zero and always runs straight at their targets, the total distance each travels must be s.  (Equivalent to, but easier than the poser's analysis, which uses the origin.  It obviously generalizes to the n-gon.)
3. Is not well-posed until you tell me how big a dog's nose is--when the dogs bump noses, how far are they from the center of the square.  For ideal mathematical point dogs, the  direction is indeterminant because they circle the meeting point infinitely often as they approach it. But they still do meet!
Title: Re: Heet seeking missiles
Post by towr on May 21st, 2008, 10:18am

on 05/21/08 at 09:21:02, snow wrote:
2. Becomes easy if you look from the point of view of one of the dogs, who at any instant sees another dog directly ahead and runs toward it at full speed (which we will assume is 1).  Since dogs start at distance s apart and end at distance zero and always runs straight at their targets, the total distance each travels must be s.  (Equivalent to, but easier than the poser's analysis, which uses the origin.  It obviously generalizes to the n-gon.)
I'm not convinced. In the case of a square I'll buy it, because the direction the pursued dog moves in is always perpendicular to the direction of the pursuing dog; but for other N-gons I remain skeptical.
Title: Re: Heet seeking missiles
Post by snow on May 21st, 2008, 12:18pm

on 05/21/08 at 10:18:08, towr wrote:
I'm not convinced. In the case of a square I'll buy it, because the direction the pursued dog moves in is always perpendicular to the direction of the pursuing dog; but for other N-gons I remain skeptical.

Thanks; I hadn't really thought through the n-gon case.  The generalization would have to take that into account by subtracting the pursued dog's velocity vector away from the pursuing, which is 0 in the case of a square, as you point out.  
Title: Re: Heet seeking missiles
Post by ThudanBlunder on May 21st, 2008, 4:21pm

on 05/21/08 at 10:18:08, towr wrote:
I'm not convinced. In the case of a square I'll buy it, because the direction the pursued dog moves in is always perpendicular to the direction of the pursuing dog; but for other N-gons I remain skeptical.

For a regular n-gon I think time taken T = r/Vsin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/n) and distance travelled S = VT = r/sin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/n)
Title: Re: Heet seeking missiles
Post by Grimbal on May 23rd, 2008, 2:57am

on 03/17/06 at 15:03:18, Icarus wrote:
I don't buy this argument. It is true that the angle would have to be infinite, but this is not impossible if the radius goes to zero.

Mathematically, maybe.  But if the speed remains constant and the curvature goes to infinity, the acceleration of the missiles goes to infinity.  If the missiles are unable of infinite acceleration they would probably end up chasing around in a circle or loose track of each other.
Title: Re: Heet seeking missiles
Post by steenreem on Jun 20th, 2008, 9:12am
I tried a different approach but failed.

I set the origin of my system at the lower left corner of the square. I name the x and y of the missile that starts in the lower left corner x1 and y1; and I name those of the missile it faces, which is above it, x2 and y2.

Because of symmetry, at all times this must be true: y1 = x2
x1 = -y2 + s   (missile 2 starts at (0,s))

and because missile1 moves towards missile2:
dy1/dx1 = (y2-y1)/(x2-x1)
= (s-x1-y1)/(y1-x1)
--> dy1 (y1-x1) = dx1 (s-x1-y1)
and by integrating
--> 1/2*(y1)^2 -x1y1 = sx1 - 1/2*(x1)^2 - x1y1
--> (y1)^2 = -(x1)^2 + 2*sx1

This says that when x=0 then y=0, which it should be. But when x=1/2s then y = Root(3/4s)
Noo!

What's wrong here?
Title: Re: Heet seeking missiles
Post by rmsgrey on Jun 20th, 2008, 9:40am

on 06/20/08 at 09:12:32, steenreem wrote:
I tried a different approach but failed.

I set the origin of my system at the lower left corner of the square. I name the x and y of the missile that starts in the lower left corner x1 and y1; and I name those of the missile it faces, which is above it, x2 and y2.

Because of symmetry, at all times this must be true: y1 = x2
x1 = -y2 + s   (missile 2 starts at (0,s))

and because missile1 moves towards missile2:
dy1/dx1 = (y2-y1)/(x2-x1)
= (s-x1-y1)/(y1-x1)
--> dy1 (y1-x1) = dx1 (s-x1-y1)
and by integrating
--> 1/2*(y1)^2 -x1y1 = sx1 - 1/2*(x1)^2 - x1y1
--> (y1)^2 = -(x1)^2 + 2*sx1

This says that when x=0 then y=0, which it should be. But when x=1/2s then y = Root(3/4s)
Noo!

What's wrong here?

Looks about right for the first time the missile crosses x=1/2, though I haven't checked the actual path involved. The catch is that the missile spirals around (1/2,1/2) for an infinite number of loops, so the actual path takes an infinite number of values of y at x=1/2.

Looking at your working, the derivative is discontinuous whenever x1=x2, so you'd expect there to be problems there.
Title: Re: Heet seeking missiles
Post by NightBreeze on Jun 20th, 2008, 4:31pm
Hello everyone.

I looked into this particular problem today and think I came up with a solution to the simple case (the square starting position).

First off, let's introduce some notation.

I numbered the missiles 1 through 4 starting with the lower right one. Of course this doesn't really matter because of all the symmetry, but just to be clear. I chose my origin to be the center of the square with a radius r. Missile number 1 is consequently located at (s,-s) at the start, with s = r/Sqrt[2]

The first thing to note is that, because of the symmetry, there is a 90 degrees angle between the lines connecting 2 adjacent missiles and the origin at all times. Furthermore, all the missiles are at the same distance from the origin at all times as well. Let (x,y) be the position of missile 1 and (x2,y2) be the position of missile 2. Then we know that, because of symmetry,

x = -y2
y = x2

Because we know the velocity of missile 1 is of constant magnitude and directed towards missile 2 at all times, we can find the direction of the velocity of missile 1 directly from its location. Let v0 be the speed of the missile and let v : http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/longrightarrow.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif be the velocity  of missile 1 at some point (x,y). Note that since we are only interested in the length of the path the missile will describe, the magnitude of the velocity is of no interest. To be precise, we would have to find the direction of the velocity, normalize it and then multiply it by v0. But since that will only complicate things, it can be omitted. So

v(x,y) = (x2 - x, y2 - y)

We can use the identities found above to express this in terms of the position of missile 1 only.

v(x,y) = (y - x, -x - y)


Note that this equation describes a vector field. Let p : http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/longrightarrow.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif : p(t) = (x(t),y(t)) be the position (x,y) of missile 1 at a time t, then p'(t) = v(t). So

dx/dt = y - x
dy/dt = - (y + x)

The general solution for this differential equation is

x(t) = Aehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[cos(t) - sin(t)]
y(t) = -Behttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[cos(t) + sin(t)]

Using the boundary condition p(0) = (s,-s), we find that A = B = s.


Having found the function p(t) that describes the flow line through the velocity vector field starting at (s,-s), we can integrate along its path to find the distance travelled. We have to find

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sub0.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif ||p'(t)|| dt

Note that p'(t) = v(t), so

||p'(t)|| = ||v(t)|| = Sqrt[ (y-x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif + (-y-x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif ]

Furthermore,

(y-x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[-2cos(t)]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif
                    = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif(4coshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gift)
                    = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[2 + 2cos(2t)]

and

(-y-x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[-2sin(t)]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif
                    = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif(4sinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gift)
                    = shttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif[2 - 2cos(2t)]


Now we can substitute these into the expression for ||p'(t)|| and integrate from t = 0 through http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif to find the desired distance traveled.

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sub0.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif ||p'(t)|| dt = 2s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sub0.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif ehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif dt = 2s


We find that the distance is 2s. Substituting s = r/Sqrt[2], we find

d = rSqrt[2]


An n-gon would have a different rotational angle. I will look into that tomorrow
Title: Re: Heet seeking missiles
Post by NightBreeze on Jun 21st, 2008, 4:15am
I looked into the generalized case of the n-gon today and came up with a solution to that one as well. It is the same as found by ThundanBlunder and jollytail.

The origin of my coordinate system is at the center of the n-gon.
In the case of N missiles, the angle of rotation to go from missile 1 to missile 2 is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif = 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N. We can stick this into the clockwise rotation matrix to find (x2,y2) in terms of the position (x,y) of missile 1.

x2 = xcoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif + ysinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif
y2 = ycoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - xsinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif

As before, the direction of v is that of the vector connecting (x,y) and (x2,y2). So

dx/dt = x2 - x = xcoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif + ysinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - x
dy/dt = y2 - y = ycoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - xsinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - y

These differential equations can be solved explicitly, using the boundary condition that x(0) = s, y(0) = s with s = r/Sqrt[2]. It does not matter what the initial position of missile 1 is, as long as its a distance r from the origin. The equations are rather large, so to make the math more readable, define the following:

k = 1 - cos(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N) > 0
c = sin(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N)

The solution to the differential equations is then given by

x(t) = sehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif [cos(ct) + sin(ct)]
y(t) = sehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif [cos(ct) - sin(ct)]


Now to find ||p'(t)|| = ||v(t)|| = Sqrt[ (xcoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif + ysinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif -x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif + (ycoshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - xsinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif - y)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif ]

...algebra...

= Sqrt[ 2k(xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif + yhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif) ]
= Sqrt[ 2kshttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif*2ehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif ]
= 2Sqrt[k]ehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif

This can be integrated from 0 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif


http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sub0.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif ||p'(t)|| dt = 2sSqrt[k]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sub0.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gifehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supminus.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supk.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supt.gif dt = 2s/Sqrt[k]

Substituting back s = r/Sqrt[2] and k = 1 - cos(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N) = 2sinhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N), we get

d = 2s/Sqrt[1 - cos(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N)] = Sqrt[2]r/(Sqrt[2]sin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N)

= r / sin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/N)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board