Author |
Topic: Heet seeking missiles (Read 10947 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
Heet seeking missiles
« on: Mar 17th, 2006, 1:05pm » |
 Quote  Modify
|
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.
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.
Nevertheless the path can be described and it's length has a finite value.
The lenght is the easier:
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.
The path:
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.
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 1/sin(pi/N), while the path is r=exp(Alpha*tan(pi/N)).
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Heet seeking missiles
« Reply #1 on: Mar 17th, 2006, 3:03pm » |
Quote Modify
|
on Mar 17th, 2006, 1:05pm, 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Heet seeking missiles
« Reply #2 on: Mar 18th, 2006, 12:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
snow
Newbie
Gender:
Posts: 2
|
|
Re: Heet seeking missiles
« Reply #3 on: May 21st, 2008, 9:21am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heet seeking missiles
« Reply #4 on: May 21st, 2008, 10:18am » |
Quote Modify
|
on May 21st, 2008, 9:21am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
snow
Newbie
Gender:
Posts: 2
|
|
Re: Heet seeking missiles
« Reply #5 on: May 21st, 2008, 12:18pm » |
Quote Modify
|
on May 21st, 2008, 10:18am, 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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Heet seeking missiles
« Reply #6 on: May 21st, 2008, 4:21pm » |
Quote Modify
|
on May 21st, 2008, 10:18am, 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( /n) and distance travelled S = VT = r/sin(/n)
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Heet seeking missiles
« Reply #7 on: May 23rd, 2008, 2:57am » |
Quote Modify
|
on Mar 17th, 2006, 3:03pm, 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.
|
| « Last Edit: May 23rd, 2008, 2:58am by Grimbal » |
IP Logged |
|
|
|
steenreem
Newbie
Posts: 1
|
|
Re: Heet seeking missiles
« Reply #8 on: Jun 20th, 2008, 9:12am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Heet seeking missiles
« Reply #9 on: Jun 20th, 2008, 9:40am » |
Quote Modify
|
on Jun 20th, 2008, 9:12am, 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.
|
|
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Heet seeking missiles
« Reply #10 on: Jun 20th, 2008, 4:31pm » |
Quote Modify
|
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 :    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 : : 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) = Ae  [cos(t) - sin(t)]
y(t) = -Be[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
   ||p'(t)|| dt
Note that p'(t) = v(t), so
||p'(t)|| = ||v(t)|| = Sqrt[ (y-x) + (-y-x) ]
Furthermore,
(y-x) = se[-2cos(t)]
= se(4cost)
= se[2 + 2cos(2t)]
and
(-y-x) = se[-2sin(t)]
= se(4sint)
= se[2 - 2cos(2t)]
Now we can substitute these into the expression for ||p'(t)|| and integrate from t = 0 through  to find the desired distance traveled.
||p'(t)|| dt = 2s e 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
|
| « Last Edit: Jun 21st, 2008, 5:07am by NightBreeze » |
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Heet seeking missiles
« Reply #11 on: Jun 21st, 2008, 4:15am » |
Quote Modify
|
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  = 2/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 = xcos + ysin
y2 = ycos - xsin
As before, the direction of v is that of the vector connecting (x,y) and (x2,y2). So
dx/dt = x2 - x = xcos + ysin - x
dy/dt = y2 - y = ycos - xsin - 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(2/N) > 0
c = sin(2/N)
The solution to the differential equations is then given by
x(t) = se [cos(ct) + sin(ct)]
y(t) = se [cos(ct) - sin(ct)]
Now to find ||p'(t)|| = ||v(t)|| = Sqrt[ (xcos + ysin -x) + (ycos - xsin - y) ]
...algebra...
= Sqrt[ 2k(x + y) ]
= Sqrt[ 2ks*2e ]
= 2Sqrt[k]e
This can be integrated from 0 to
||p'(t)|| dt = 2sSqrt[k]e dt = 2s/Sqrt[k]
Substituting back s = r/Sqrt[2] and k = 1 - cos(2/N) = 2sin(/N), we get
d = 2s/Sqrt[1 - cos(2/N)] = Sqrt[2]r/(Sqrt[2]sin(/N)
= r / sin(/N)
|
| « Last Edit: Jun 23rd, 2008, 3:58am by NightBreeze » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print