Waste less time on Facebook — follow Brilliant.
×

Capture the Pirate Ship !

You're on a government ship, looking for a pirate ship. You know that the pirate ship travels at a constant speed, and you know what that speed is. Your ship can travel twice as fast as the pirate ship. Moreover, you know that the pirate ship travels along a straight line, but you don't know what that line is. It's very foggy, so foggy that you see nothing. But then! All of a sudden, and for just an instant, the fog clears enough to let you determine the exact position of the pirate ship. Then, the fog closes in again and you remain (forever) in the thick fog. Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction. How will you navigate your government ship so that you will capture the pirate ship?

Note by Abhishek Sinha
4 years ago

No vote yet
21 votes

Comments

Sort by:

Top Newest

Duh you have very complicated solution... your formulas and whatever is that is only applicable if our world is flat..

Since the Earth is a sphere, just go to the point where the pirate ship was and wait. The pirate ship is traveling along a straight line (one of the great circles), so eventually it will come back around to the same point.

The speed of the ships doesn't matter at all. :-P Mharfe Micaroz · 4 years ago

Log in to reply

@Mharfe Micaroz Since you have brought in topology, note that your solution will only work if every geodesic is a closed curve (global property), while Abhishek uses local coordinates. Can you give a classification of all such surfaces? Of course, a necessary condition is that the surface is bounded, but this is not sufficient.

As a (contrived) example: Brilli the ant and it's playmate were playing on a (magically suspended) doughnut (which we will assume is a perfect torus). Some evil human sprays insecticide and blinds the both of them (so all they know is the initial distance). If the playmate decides to run straight at a constant speed, can Brillit the ant ever find it's playmate? Calvin Lin Staff · 4 years ago

Log in to reply

@Calvin Lin Walk forward slowly Daniel Leong · 4 years ago

Log in to reply

@Calvin Lin I don't have any idea what are you talking and honestly I don't know topology. I am just an educator specifically a high school teacher not a total MATH major. I guessed someone out there can still give solutions to that kind of problem even w/o the knowledge of the so-called "Topology", equipped only with pure COMMON SENSE, and simple LOGIC. So, I am so sorry I cannot answer your follow-up questions Mr. Calvin L. .... Mharfe Micaroz · 4 years ago

Log in to reply

@Mharfe Micaroz Your answer is based on the fact that on a sphere, all geodesics (locally the shortest distance between any 2 points) are the great circles. As such, this allows us to conclude that the pirate ship must eventually return back to the starting point.

However, this doesn't necessarily hold true on other surfaces. An obvious example is the 2-D plane, in which no geodesic is closed. As such, I raised the natural followup question, asking for what kind of surfaces are all geodesics closed, which would allow for your argument to hold true, instead of requiring the mechanics solution that was presented.

For example, if you consider the torus (i.e. doughnut), does there exist a geodesic that is infinitely long? As it turns out, there does (Find one! Be irrational), even though the doughnut a bounded figure. As such, if Brilli the Ant were to sit around waiting, it is possible for her playmate to never come back, even though the two of them might get infinitely close to each other. Calvin Lin Staff · 4 years ago

Log in to reply

@Calvin Lin tnx Calvin, now I am curious with Topology already...:) Mharfe Micaroz · 4 years ago

Log in to reply

@Mharfe Micaroz Wow ! That's a clever reply :) Abhishek Sinha · 4 years ago

Log in to reply

@Abhishek Sinha Thanks. Simplifying things is my job as an educator. Why make things complicated if you could actually make it simpler?:) That's a very nice question you posted above Abhishek. Mharfe Micaroz · 4 years ago

Log in to reply

@Mharfe Micaroz Although your answer is acceptable, I originally posed the problem for the conventional flat land world. As it is mathematically interesting, can you throw some light on it ? Abhishek Sinha · 4 years ago

Log in to reply

@Mharfe Micaroz The ship could be heading due North East, for example. Then it would traverse a loxodrome, not a great circle. Eric Edwards · 4 years ago

Log in to reply

@Eric Edwards A rhumb line isn't a straight line on a sphere. "Straight line" implies a great circle, if you assume a spherical space.

A rhumb line is a line of constant heading though, so if the original problem had said that the pirate ship has a constant speed and heading, then you'd have a point. Jordan Bettis · 4 years ago

Log in to reply

Let \( (0,0) \) - the origin, be the point where the pirate ship was located when you saw it. Then, choose some \(R\) and make sure you can reach the point \( (R,0) \) in time \( \frac{R}{v} \) Wherever you were located in the beginning, you can choose a large enough \( R \) so that you reach \( (R,0) \) before a pirate ship would. Then, set time \(t = 0\) and start moving in a spiral described by polar coordinates \( (R + vt , \omega t)\) and make sure you choose a small enough value of \( \omega \) so that your speed does not exceed \( 2 v \). This is how you make sure you catch the pirate ship no matter in which direction \( \phi \) it is travelling. Ivan Stošić · 4 years ago

Log in to reply

@Ivan Stošić What if \(\phi=0\) ? Also, please provide a detailed mathematical proof that they meet in some finite time. Abhishek Sinha · 4 years ago

Log in to reply

@Abhishek Sinha Let me formalize what Ivan S. is saying: Note that all coordinates are in polar.

Orient the coordinate system such that the pirate ship is at the origin and your ship is at \((3R,0)\), where \(R\) is one-third the distance between your ship and the pirate ship. Let the path of the pirate ship be \(p(t) = (vt,\phi)\) where \(v\) is the pirate ship's speed and \(\phi\) is it's direction.

Let \(g(t) = \begin{cases} \left(3R - 2vt,0\right) & \text{for} \ 0 \le t \le \tfrac{R}{v} \\ \left(vt , \omega (t - \tfrac{R}{v})\right) & \text{for} \ \tfrac{R}{v} \le t \le \tfrac{R}{v} + \tfrac{2\pi}{\omega} \end{cases}\) be the government ship's path.

(This path first heads straight toward the pirate ship's initial location, then spirals outward.)

Clearly, \(g(0) = (3R,0)\), and \(g(\tfrac{R}{v}^{-}) = g(\tfrac{R}{v}^{+}) = (R,0)\).

For \(0 \le t \le \tfrac{R}{v}\), the speed of the government ship is exactly \(2v\).

For any \(\phi \in [0,2\pi]\) let \(t_{\phi} = \dfrac{R}{v} + \dfrac{\phi}{\omega}\). It is easy to verify that \(p(t_{\phi}) = g(t_{\phi})\) for all \(\phi \in [0,2\pi]\).

However, for \(\tfrac{R}{v} \le t \le \tfrac{R}{v} + \tfrac{2\pi}{\omega}\), the speed of the government ship is:

\(\sqrt{\left(\dfrac{dr}{dt}\right)^2 + \left(r\dfrac{d\theta}{dt}\right)^2} = \sqrt{\left(v\right)^2 + \left(vt \cdot \omega \right)^2} = v\sqrt{1 + (\omega t)^2} \le v \sqrt{1+4\pi^2} \approx 6.36v\).

So, the government ship must be able to travel more than 6 times as fast as the pirate ship to use this strategy. Thus, this method won't quite work. But it is a good start. Jimmy Kariznov · 4 years ago

Log in to reply

@Jimmy Kariznov That's good. To take it further, can you obtain a differential equation for Government Ship's trajectory, from which you will be able to analytically solve for \(r(\theta)\) ? Abhishek Sinha · 4 years ago

Log in to reply

@Abhishek Sinha Let \(g(t) = (3R - 2vt,0)\) for \(0 \le t \le \tfrac{R}{v}\) and \(g(t) = \left(r(t), \theta(t)\right)\) for \(t \ge \tfrac{R}{v}\).

We want \(r(t) = vt\) for \(t \ge \tfrac{R}{v}\) and \(\theta(t)\) to range from \(0\) to \(2\pi\) in a finite time.

This will guarantee that the pirate ship is eventually caught.

If the government ship travels at the maximum speed for that duration, then:

\((2v)^2 = \left(\dfrac{dr}{dt}\right)^2 + \left(r\dfrac{d\theta}{dt}\right)^2 = (v)^2 + \left(vt \dfrac{d\theta}{dt}\right)^2 \leadsto \dfrac{d\theta}{dt} = \dfrac{\sqrt{3}}{t}\).

Using the condition \(\theta(\tfrac{R}{v}) = 0\), we have \(\theta(t) = \sqrt{3}\ln\left(\tfrac{vt}{R}\right)\).

So, let \(g(t) = \left(vt, \sqrt{3}\ln\left(\dfrac{vt}{R}\right) \right)\) for \(t \ge \tfrac{R}{v}\), and let \(t_{\phi} = \dfrac{R}{v}\exp\left(\dfrac{\phi}{\sqrt{3}}\right)\).

Then, \(g(t_{\phi}) = p(t_{\phi})\) and thus, the pirate ship gets caught by \(t_{2\pi} = \dfrac{R}{v}e^{2\pi/\sqrt{3}}\). Jimmy Kariznov · 4 years ago

Log in to reply

@Jimmy Kariznov Also, it takes \(\tfrac{2\pi R_{\text{earth}}}{v}\) for the pirate ship to travel a great circle. If the initial distance to the pirate ship is less than \(6\pi e^{-2\pi/\sqrt{3}} R_{\text{earth}} \approx 3190 \ \text{km}\), then this method is faster than waiting for the pirate ship to travel a great circle. Jimmy Kariznov · 4 years ago

Log in to reply

@Jimmy Kariznov The main question of the problem:

"How will you navigate your government ship so that you will capture the pirate ship?"

Its about capturing, not finding the fastest route or speed.:) Mharfe Micaroz · 4 years ago

Log in to reply

@Jimmy Kariznov Awesome ! Abhishek Sinha · 4 years ago

Log in to reply

@Jimmy Kariznov Just came back here to tell you that \( \omega \) need not be constant but you beat me to it, and you finally made a complete solution. Thanks! Ivan Stošić · 4 years ago

Log in to reply

@Ivan Stošić ? Jason Kang · 4 years ago

Log in to reply

@Jason Kang Frankly, I do not understand your question. Ivan Stošić · 4 years ago

Log in to reply

@Ivan Stošić There was no question! :) Abdullah Sherif · 4 years ago

Log in to reply

I got the answer (without any topology and other complex earth models)but apparently someone has already posted a similar one already, though in complex mathematical terms. So I will try to put it in a simple, lucid fashion for everyone. 1) First of all, the govt ship(our ship) should move to the exact point where pirate ship was seen.

2) Now realize that the pirate ship is located on a circle of radius 'r' the value of which is equal to distance travelled by pirate ship from the time we left i.e r = v * d / 2v = d/2=0.5d where 'd' is the initial distance between our ship and pirate ship. And now this radius is increasing with time linearly.

3) Since we don't know the direction, we would first decide to reach at the same radius as the pirate ship. For that we need to travel in any arbit direction(say horizontal) for time 'T1' where T1 = r / relative radial speed
or T1= 0.5d / v

4) Now we are located on the same circle on which pirate ship is located. The centre of the circle is the point where we saw the pirate ship in the 1st step. Now comes the important part. In order to catch the pirate ship from here, we need to remain on the same circles on which this pirate ship is travelling which means that our ship needs to go with the same radial velocity ' v ' ( i.e. ' v ' away from the centre). With the radial speed in place we need to monitor the other angles as well so that we can find the ship. The remaining perpendicular component of our velocity ' 2v ' would be ' (3)^0.5 v ' (i.e root of 3 multiplied by v). This is the angular component of velocity.

Done!!

So, with ' v ' as our radial velocity and (3^0.5) v as our angular velocity, we would remain on the same circle on the ship meeting it at some point.

If you want to know the hard mathematics i.e equation for this curve in polar coordinates you can specify it as follows: Assume the point where we first saw the ship to be (0, 0) and we are at angle, say 'm' = 0. Start the clock, t = 0. Then the radial coordinate ' r ' of our ship at any time ' t ' is given by r = v * t + 0.5d ---------------------------> Equation 1 and the angular coordinate(m) is related to time as : r dm = (3)^0.5 dt or dm = (3)^0.5 dt / (v * t + 0.5d) [using equation 1] Integrating this equation, Angular coordinate(theta) m = { (3)^0.5 / v } * ln( v * t + 0.5 d) ---------------------------> Equation 2

Now we can eliminate ' t ' from equation 1 and equation 2 to get the equation for the trajectory whcih gives m = k ln(r) where k is a constant that depends on ' v ' and equals m = (3)^0.5 / v

I hope the simplified solution helps!!

Regards Aayush Aayush Gupta · 4 years ago

Log in to reply

intuitively i feel that if it followed a spiral trajectory,it could catch the ship. Soham Chanda · 4 years ago

Log in to reply

i will travel towards in the direction towards which the ship was pointing.the direction towards which the ship was pointing is the direction in which the ship was traveling because the ship is going in a straight line.there is your answer. Bodhisattya Dutta · 4 years ago

Log in to reply

I think the solution is quite easy.The government ship should follow a spiral path.This is because the government ship can not follow a fixed direction.If it follows a circular path then the pirate ship may easily escape.As the speed of the government ship is twice the speed of the pirate sheep as it knows the position as well as the speed of the pirate ship it may try to continuously increase the radius of the circle that it should have followed.This will give a spiral path.Any direction the pirate ship should have gone the government ship will be able to put it inside the spiral path as its speed is larger than the speed of the the pirate ship and hence after a certain time capture it easily. Adhiraj Mandal · 4 years ago

Log in to reply

sir , i didnt get any prizes from brilliant Ratan Rock · 4 years ago

Log in to reply

Given the pirate ship's known location and the time from when it was sighted, you know a circular path that contains the current location of the pirate ship. That circle gets larger as time goes on. The government ship just needs to head toward the pirate ship's sighted location, but once it intersects the growing circular path for the current time, the government ship picks a direction and follows the growing circle that matches the current time. The course of the government ship will be a spiral. The government ship will meet the pirate ship before completing a 360 degree rotation. Danrlley Maciel · 4 years ago

Log in to reply

The most intuitive and ,logical approach would be to spiral in on the pirate ship starting from a circle of some radius r = s*t where s = speed of the pirate ship and t is some reasonable value for the maximum time till the ship is captured. One reasonable value is the distance between the 2 ships at the time the bearing is obtained / difference in speeds Of course, one could take the distance between the 2 ships as the radius Sundar R · 4 years ago

Log in to reply

I have obtained a solution(assuming flat sea and ignoring comple topology stuff). Apparently, someone else posted the correct answer already, nevertheless I would try to present my soultion in a simple and lucid manner. So reaching the ship can be done in 4 steps:

1) The government ship(our ship) should reach the point 'O' where the pirate ship was seen.

Now realise that at this instant, the pirate ship is located on a circle with centre at the point 'O' and radius equal to 0.5d (where 'd' is the initial distance between govt. ship and pirate ship) because it covers half the distance transversed by our ship 'd'

2) In order to reach this ship, we first try to reach the same radial location as the pirate ship. For that we move in any arbitary direction (say horizontal direction) so that we are at the same radius as the pirate ship. This would require us to travel with velocity ' 2v ' (where ' v ' is velocity of the pirate ship) for a time interval 'deltaT' equal to deltaT = (Distance between the ships) / (Relative radial speed of our ship w.r.t. pirate ship) = 0.5d / v So, after travelling for time 'deltaT' in horizontal direction, we reach a point 'P'

3) Once we have reached this point 'P', we are on the same radius circle as the pirate ship. Now starts the interesting part!! In order to reach the pirate ship, we need to ensure that we remain on the same circle as the pirate ship. For that purpose, we keep our radial speed equal to that of pirate ship i.e ' v '

4)Simultaneously, we need to be able to scan different angular points as well. For that keeping our radial speed ' v ' of step 4, we use the remaining component of our velocity (3)^0.5 * v in the tangential direction to scan various points on the circle.

DONE !! In this way, with radial velocity as ' v ' we ensure remaining on the same radial distance from 'O' as the pirate ship while simultaneously trying to find it on the circle with angular velocity (3)^0.5 * v


Now, if you want to know the trajectory on which our ship should move, you may want to see the below mathematics.

Assume 'O' as origin (0,0). Start the time t=0 when we reach 'P' Now radial coordinates of P are (0.5d, 0 )

To get equation for our curve, the radial coordinate is given by: r = v * t + 0.5d ----------------------------------------------------------> Equation 1

And angular coordinate 'm' is given by: rdm = (3)^0.5 * dt or dm = (3)^0.5 * dt / (v * t + 0.5d) (using equation 1)

Integrating this equation we get: m = [ (3)^0.5 / v ] * ln (v * t + 0.5d) -----------------------------------------------------------> Equation 2

Eliminating ' t ' from Equation 1 and Equation '2', we get the trajectory equation in polar coordinates:

m = [ (3)^0.5 / v ] * ln(r)

Hope that helps in understanding the solution better.

Regards Aayush Aayush Gupta · 4 years ago

Log in to reply

Not sure if this has already been posted, but here's what I was thinking (assuming a flat world with no land): Let S be the point at which the pirate ship was spotted. As soon as you see the ship, start towards S. Let N be the distance in feet from the point you were at when you saw the ship to S. Since the ship moves at half your speed, by the time you reach S, the ship will have moved N/2 feet away from S. Keep going N feet past S. When you are done, the ship will have traveled N/2 more feet, making it a total of N feet away from S, the same as you. Now you and the ship are at points on the circle defined by center S and radius N. Start on a path defined by one turn of a spiral with inner radius N such that with the arc length of one turn being P (which would obviously have to be greater than pi*N^2), the radius increases by P/2 every turn and increases at a constant rate. You should be able to catch the pirate ship in this one turn.

This seems like close to the fastest method to me in normal condition, and assuming no enormous amount of luck.

Would this work? Is there anything wrong with that reasoning? I wasn't sure how to express it in fully formal terms. Thanks. Vishnu Menon · 4 years ago

Log in to reply

I think searching in a spiral should work in all topologies where circumference is not superlinear in diameter. Informal argument:

  1. Go to the pirate ship's original position \( O \), and proceed at speed \( 2v \) for the same length of time it took for you to get to that position. You're now on the same circle (broadly defined as the locus of points some distance away from a specific point) as the pirate ship.
  2. Take alternating infinitesimal steps outward and left along whatever circle around \( O \) you're currently on.

Because circumference is bounded above by some factor of diameter (call it \( p \) ), if you are t units away from O you will move left along the circle at least \( \frac{\epsilon}{t} \) radians. Since \( \frac{\epsilon}{t} \) is a diverging series, the sum will eventually pass \( p \) radians, so you will have travelled the full circle around.

The above argument certainly has holes in it - particularly it assumes that there is a concept of "angle" which is a function mapping points to \( [0,p) \) such that moving along any straight line passing through \( O \) does not change the function's value. But the reasoning seems like it should hold somehow; anyone have ideas on how to formalize it? Vitalik Buterin · 4 years ago

Log in to reply

go to where you saw it and wait for it to come around again Tia Breed · 4 years ago

Log in to reply

I can't and I won't formalize my idea but it seems to me that describing a spiral, which center is the position where the pirate ship was spotted, and in a way that your ship is, at any time distant (relative to that point) of V*t (where V is the speed of the pirate ship and t the time elapsed since you spotted it), you will catch it sooner or later (most likely later)! Clément Robert · 4 years ago

Log in to reply

You just search in a spiral around them. Daniel Leong · 4 years ago

Log in to reply

Maybe this is not a mathematically solution but it worth a shot. I think if you can determine the position of the pirate ship in an instance, there are 2 possibilities, you know it by seeing the radar (although you can locate it without the fog disappear) or you can see it with your eyes. If it is the first possibility then you already know the speed and the location. You just have to find it's direction. Because you're in a government ship, you can gather all information necessary around the world where the last time the pirate ship is seen in a pier and you can determine the direction of the ship because the ship travel along a straight line and with a right calculation you can determine how the government ship have to travel and catch the pirate ship. If it second possibility, then it is a bit harder because you still can’t determine how far the pirate ship from government ship. But still you can see the direction of the ship. So you only have to do is estimate how far the pirate ship from the government ship and make the calculation for pursue the pirate ship. I thought this would be easier because if you can see the ship it means the ship is near. Muhammad Shafarifky · 4 years ago

Log in to reply

does capturing means intersecting with the ship or passing by it through a certain distance..? Raghav Chhabra · 4 years ago

Log in to reply

Ouch. Before I came here to say the answer is SPIRAL - a good dozen people came before. Er. Never,ind. It's a simple answer anyway. Yuri Ammosov · 4 years ago

Log in to reply

Are we talking about modern-day pirates or olden-day pirates? Olden-day I don't know, but modern-day...if you are a government ship, you have some sort of radar. Just speed quickly to the position where the ship was. It should be very easy to determine where the ship is, and very easy to catch up, since you can travel twice as fast and the ship is half as close to that position as you were when the fog cleared. Angel Cooper · 4 years ago

Log in to reply

From what I've read, I think these assumptions apply:

-The world can be modeled as a Cartesian plane, i.e. an infinite flat surface.

-There is no dry land, shallow water, storm, or any other obstacle that will prevent the ships from following their paths.

-Ships normally travel in the direction they are facing; hence, the direction of the pirate ship can be determined once it is seen.

If these assumptions apply, then plane trigonometry will be enough to solve the problem. Just travel in a straight line, the direction of which will be determined by the direction that the pirate ship is facing. (I haven't done calculations yet, though.) Francis Gerard Magtibay · 4 years ago

Log in to reply

@Francis Gerard Magtibay The problem is way more interesting if you don't know the direction of the pirate ship. Tim Vermeulen · 4 years ago

Log in to reply

@Francis Gerard Magtibay From the problem statement: "Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction."

So, you don't know which direction it is facing. Jimmy Kariznov · 4 years ago

Log in to reply

@Jimmy Kariznov Okay, in that case let's drop David L.'s assumption that the pirate ship will travel in the direction it is facing. It doesn't make sense though. :D Francis Gerard Magtibay · 4 years ago

Log in to reply

@Francis Gerard Magtibay It may travel in the direction it is facing, but you just don't know what direction it's facing. Tim Vermeulen · 4 years ago

Log in to reply

Use Jack Sparrow's compass Vincent Miller Moral · 4 years ago

Log in to reply

if i am going to catch a pirate ship.......i wld hve taken any instrmnt or device to record its movement even in the slightest possible span of time........this wld prvde me the directn as well as position....... C.K. Raman · 4 years ago

Log in to reply

You must be incredibly stupid/short-sighted to not be able to see which end is the front. David L. · 4 years ago

Log in to reply

@David L. What if the ship is too far away to tell which direction it is facing? Jimmy Kariznov · 4 years ago

Log in to reply

@David L. It's remarkably difficult to judge the direction of ships from a distance. Hell, there were entire naval camouflage systems that relied entirely on making it even harder. Sam Ford · 4 years ago

Log in to reply

@Sam Ford Also remember the pirates can't steer Daniel Leong · 4 years ago

Log in to reply

@David L. so just overtake it! Daniel Leong · 4 years ago

Log in to reply

let the fools run onto land David L. · 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...