This problem was extra credit for a college math class. Don’t worry though, the term is over. You won’t be helping anyone cheat! Damned if I can figure it out though.
A space traveller (call him Spiff) is riding in his space car exploring a strange planet seemingly covered entirely in sand dunes. After a short distance the space ship is totally obscured by the dunes, but Spiff isn’t worried because he trusts his instruments. That turns out to be a bad idea since he dozes off and is awakened by an alarm telling him that the navigational unit has malfunctioned, and he finds his car driving in a tight circle. All he knows is that he has travelled 1000 km in a straight line from his ship, though he doesn’t know in which direction. He also sees that he has 6400 km worth of fuel to find his way back. Fortunately, the compass and odometer are working perfectly so he will be able to travel any direction he chooses for as far as he chooses. Also, he knows his ship is on a coastline, which continues for a straight line for thousands of kilometers in either direction. What should be his strategy for guaranteeing his survival?
Now, the problem didn’t state it, but I think we can assume there are no tracks to follow. I also think the planet is either totally flat, or at least large enough that the curve of the orb isn’t relevant.
What do you mean? He’s doing donuts (driving in a tight circle) while he dozes, but awakens to find himself 1000 km in a straight line from the ship? Maybe the question IS FAILING TO SAY that the planet is so small that the circles he drove while dozing were really circles along the contour of the planet. So, maybe the distance (d) he drove is 1000 km, but his displacement (s) from the ship could very well be a few feet…just over the dunes from where he started??? (If this is the case, maybe the trick is that the “straight path from the ship” is really a curvilinear path - using the term "straight path " loosely?) Can you clarify? - Jinx
Let’s see if I’m reading this correctly Greg Charles.
Spiff is at the center of a circle 1000k in radius, you can eliminate half the circumference since he knows the ship is on the shore line. Let’s say the sea is all to the north of the ship. Assume he is right next to the sea due east of the ship and starts going southeast, the farthest he can go (assuming he can navigate the circumference with his compass) is 2 X pi X r X 1/2 = 3141.6k. He comes to the sea and heads due east for 1000k to the ship having travelled 4141.6 k.
I’m thinking I’m wrong though, seems too easy to be a college level stumper.
And of course Spiff couldn’t know that he is to the east of the ship, so he doesn’t find it after travelling 1000k east, he has to continue east for another 2000k, for a total of 6141.6k.
As a math problem, this can’t be solved unless we assume something not in the problem.
You are in the center of a circle, the circumference of this circle is about 6,280k. The shoreline may be a tangent to this cricle, so you must reach some point on the circle and transerve the entire circle. That’s 7,280k but you only have 6,400k fuel.
If we assume some things, such as the shoreline “slices” deeply into the circle, you can some a distance. etc, then it may be possible.
The trick answer is that the folks on the space ship knows your situation and moves the ship into the circle at a right angle to the shoreline a distance permitting your fuel to be sufficient to location it.
At first glance, I can do it with less than 7000 fuel. Go straight 1155 miles, if you haven’t hit the shore line, turn 120 degrees and intercept the 1000km circle (from your starting point) and then proceed at most another 5236 km. There must be a shorter way.
I realize that it’s unlikely that the curvature of the planet matters, but here are the figures for it anyway. For a planet of infinite size, the circumference of a circle with radius 1000 km is 6283 km. For the Earth, it’s 6257 km. For the moon, it’s 5942 km.
OK, I’ll try to supply what clarification I can. The tight circles, I believe, started at the same time as the instrument failure and resulting alarm. That is, Spiff, is really 1000 km away from his ship, but doesn’t know in which direction. The sand dunes prevent seeing his ship from any great distance. He is at the center of circle of possible locations for his ship, and the coastline is tangent to that circle, which I think must be the key. If you can eliminate half the circumference because of that though, I’m missing how.
I agree with everything you said, except for this. However, it’s kind of hard to explain. The coastline would only be tangent to the circle if the direction that Spiff travelled is perpendicular to the coast itself. In the event that he travelled some other direction, then the coastline would cut through the circle.
Now, I also am inclined to think that if you solve the problem assuming that he did in fact travel perpendicular to the coast, then your solution will work in any situation. Or at least, you can easily modify it so it will work in any situation. So I have little problem with you assuming that the coast is tangent to the circle, but I do not believe that the problem as stated implies this.
I think bizerta’s on the right track, but lost marks for not showing the reasoning. We know the ship is 1000 km away, which defines a circle. We know the coastline is straight, but not that it is tangent to the circle (it could intersect the circle at 2 points if Spiff didn’t drive straight inland.
So, the first attempted solution is to drive 1000 km in a random direction, then turn either right or left and follow the circle around. This will find the ship, but if we’re unlucky and miss the ship by 1 km on the first 1000km radius and happen to turn the wrong way, we’ll have to follow the entire circumference (minus that 1 km) and run out of fuel.
So, we need to rule out some of the circle without following it. Suppose we drive due east (to the right along the x-axis on the handy-dandy mental picture which this post is unfortunately insufficient to contain, but where our initial position is the origin) for more than 1000 km. Let us be all scientific and go D km further. Let us call where we intersected the circle 0deg, and number points on the circle going counterclockwise (I have no idea what the ``normal’’ convention might be), so due north is 90deg, etc. (what I would give right now for the back of an envelope ) Let us also label this 0deg position C. So now on your own envelope, draw tangents to the circle that pass through the position 1000 + D. There will be two; one above and one below the x-axis. Label the points at which these lines are tangent to the circle A and B. Satisfy yourself that any tangent to the circle between A and B will intersect the x-axis on [0, 1000 + D], which Spiff has already travelled. Now satisfy yourself that any chord that passes through the circle twice between A and B will already have been `found’. Now, if we follow one of the tangents to A, we only need to follow the circle to B to find the shoreline. I think there may be a few special cases to deal with where the ship is between C and B, but I’m pretty confident that in any of these cases the ship will be found with less travel than 1000 + 6280 km. But I’ll leave that as an exercise
In order to minimize the distance travelled, we need to express the length of the tangent between followed in step 2 and the chunk of the circle followed between A and B all in terms of D, add them to the 1000+D that we drove in step one, differentiate the whole ugly mess wrt to D, set the slope to 0, solve for D, and check that this is in fact a minimum and not a maximum. This left as an exercise to the reader.
OK, now we’re getting somewhere. It never even occurred to me that the original travel might not have been perpendicular to the coastline, but you’re right, the problem doesn’t state that. However, I think we’ll find that perpendicular is a worst-case scenario, and so a safe assumption.
Viking, believe it or not, I followed your logic out, and I do agree with you that if the ship is between points A and B, Spiff will hit the coastline during his drive from C to D. However, A and B must be something less than half the circle. If A was at 90 degrees (following your notation) and B at -90 degrees, then the distance from C to D would be infinite, and that’s only half the circle. Your last paragraph, I don’t follow at all, though I would like to see differentiation applied to this problem somehow.
The solution I tried, which seemed to show promise was circumscribing a polygon around the circle, driving Spiff to one corner of it, then following the perimeter. The advantage of this as opposed to following the circumference of the circle, is that Spiff would not have to drive the final side of the polygon. The reason for that is buried in Viking’s explanation. However, even with a circumsribed triangle, I couldn’t get Spiff to safety within the 6400 km limit.
I think you should all abandon the idea that you are the center (don’t all people see themselves this way?) — ship is the center, and you are inscribed on the semicircle, where coast is bisector.
This is minimized for N = 7, DIST(7) = 6881.4. For some reason I’m thinking that not only would he not have to drive the final side of the polygon, but he would only have to drive one-half of the next-to-final side. If that’s the case, the formula is:
This has a minimum at N = 5, DIST(5) = 6321.9. So, if you can eliminate half of that next-to-last side, we’ve got it. Of course, I could be way off base here.
Achernar, I think you’re very close, and I haven’t checked your math, but I think you’re wrong about eliminating the final side. The worst-case scenario is when the first vertex you drive to is almost on the coast, but not quite, and you drive the wrong direction. Imagine a polygon where the last edge almost coincides with the coast, but it’s rotated just a hair. This means that the ship sits almost exactly in the center of the last polygon edge, so you have to traverse N-0.5 edges, not N-1, and certainly not N-1.5. (the problem is to get to the ship, not just to the coast)
superfreakicus, you must consider yourself at the center of the circle, since the set of possible locations for the ship is defined as the set of points 1000km from your current location. That’s a circle with you at the center.
And now for something completely different (and certainly not in the spirit of the problem): Wouldn’t spiff know the direction that the coastline runs? If so, he knows which direction to travel in order to hit it. Then it’s a matter of looking at his odometer to see how far he went (call this x), then following the coast in either direction for sqrt(1000^2 - x^2) km. If he doesn’t find the ship, turn around and go 2sqrt(1000^2 - x^2) in the other direction and he’ll be there. Worst case is when he originally traveled in a line 45 degrees off the coast, so the total distance back, including picking the wrong direction first, will be 2828km (41000*sqrt(2)/2).
But then, given the facts that the circle / circumscribed polygon solution is much more clever and appears to (possibly) just barely make it in the fuel limit, I’d say that’s in the right ballpark. My way is just too obvious, so I imagine my assumption is not allowed.
After giving this some further thought, I believe that, since you must travel all the way to the ship, not just to the coast, the circumscribed polygon method will always yield more distance traveled than viking’s A,B,C,1000+D method. You are attempting to travel to a point on the circle, so going outside the circle (aside from that initial spike which lets you eliminate a significant number of points along the circle) only serves to increase the distance traveled.
I’m starting to think that the polygon method won’t work, but what you say is not true. It’s not just going from one tangent point to the next. At each vertex, you get to eliminate another whole set of points.
Yes, but it’s the same set of points you’d eliminate by traveling through the same angle on the circle, which is less distance. You’re fooling yourself by thinking you’re eliminating points ahead on the circle when you travel out to a vertex. It is true that by traveling out to the vertex, you will discover the coastline sooner if it coincides with one of these “eliminated” points, but you don’t actually save any distance, because you’ve got to continue to the point where the coast intersects the circle anyway. Traveling on the circle would have been quicker.
On the upside, I think I discovered a flaw in your calculations on viking’s method. The distance traveled on the circle is not 2(pi - theta) × 1000, it’s 2(pi - 2*theta) x 1000 (since you effectively cut two wedges out of the circle, not one). If I’m not way off, this puts a minimum at D = 511.9, giving us a distance of 5536.7, which is way under the limit. That’s making me think I goofed the calculation.
) Let us also label this 0deg position C. So now on your own envelope, draw tangents to the circle that pass through the position 1000 + D. There will be two; one above and one below the x-axis. Label the points at which these lines are tangent to the circle A and B. Satisfy yourself that any tangent to the circle between A and B will intersect the x-axis on [0, 1000 + D], which Spiff has already travelled. Now satisfy yourself that any chord that passes through the circle twice between A and B will already have been `found’. Now, if we follow one of the tangents to A, we only need to follow the circle to B to find the shoreline. I think there may be a few special cases to deal with where the ship is between C and B, but I’m pretty confident that in any of these cases the ship will be found with less travel than 1000 + 6280 km. But I’ll leave that as an exercise