Fate of Ships
Four ships are sailing on a 2D planet in four different directions. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two?
Update June 18, 2010
Solution: Let z-axis denote time. let x- and y- axes denote the 2D planet. Then the four trajectories are straight lines. Since no collision involved more than two ships, these four lines must all lie in a plane. So, one might be tempted to believe that the two other ships will also collide. But, they might have collided in negative time. So, it cannot be decided from the given information that the two ships will collide or not?
This can be made clearer through the following two diagrams. In the first one, the four ships move such that there is no collision between the two ships. In the other diagram, the four ships move such that there is a collision between them.
Thanks to Vivek Jha (Then Junior Undergraduate, EE, IITB - Now Senior Undergraduate) for the solution
Update June 18, 2010
Solution: Let z-axis denote time. let x- and y- axes denote the 2D planet. Then the four trajectories are straight lines. Since no collision involved more than two ships, these four lines must all lie in a plane. So, one might be tempted to believe that the two other ships will also collide. But, they might have collided in negative time. So, it cannot be decided from the given information that the two ships will collide or not?
This can be made clearer through the following two diagrams. In the first one, the four ships move such that there is no collision between the two ships. In the other diagram, the four ships move such that there is a collision between them.
Thanks to Vivek Jha (Then Junior Undergraduate, EE, IITB - Now Senior Undergraduate) for the solution
Let us say ships 1 and 2 are still in commission. Then, seeing the situation from the 1st ship,
ReplyDeleteships 2 and 3 approach it along straight lines.
But both of these straight lines hit ship 1, which is just a point in this viewpoint. They also collide with each other, that must mean they are moving on the same straight line wrt 1.
A similar argument shows that to collide with both 3 and 4, 2 also has to move along the same straight line wrt 1.
Thus, 1 and 2 are doomed to collide and both will be destroyed.
Modifying Subhasis's argument.... say ships C,D sank while A,B are still sailing. Then observing from A , C & D will come on a straight line to intersect A (at different times). Now C & D also collide which means when observed from A the lines formed by them must also intersect which makes both of the collinear. Now B intersects both C & D....so when observed from A it must also form a collinear line.
ReplyDeleteWhich shows that A & B collide since these collinear lines pass through the point represented by A.
But the only problem is that this collision might have occurred in "negative" time.
So, we can't say anything conclusively about their fate.
I assume A and B are out of commission
ReplyDeletethe number below each ship is the number of times it collided with other ship.
As A and B are out of the commission their numbers will be 3 and 3 respectively.Now as the puzzle states 5 collisions have already taken place, the possible ways of number of collisons wrt each ship are
A B C D
3 3 2 2
Observe that the total collisions wrt individual ships is 10 but 5 (10/2) to a person seeing from top.
**The only possible collisions are
A-B
A-C
A-D
B-C
B-D
From above, C-D collision never occured so they may collide once in the future but they cant after one collision and hence they are safe
**Two ships cant collide more than once to each other
oops..i made a mistake..consider this
ReplyDeleteFrom above, C-D collision never occured so they may or may not collide ...
in other words fate will decide and in this case we cant predict the fate with the given information >
@Subhasis.. nice try.. This is the solution I found at Gurmeet Singh's blog.
ReplyDelete@Vivek Jha (viki).. You point out an interesting mistake. Thank You. Your solution seems correct.
@Bhanu Prakash.. What you did is wrong. If you cannot decide using your method, it does not mean that it cannot be decided. As in Vivek's solution, give a scene in which the given conditions are met and there is a collision and a scene in which the given conditions are met and there is no collision. Then only you can say that it cannot be decided.
(I already posted this on Gurmeet's page.)
ReplyDeleteThe problem says: "Their journeys started at some time in the distant past." I interpreted this to mean that if there were an accident in negative time, then this accident is already included in the said five collisions which have happened. That entails that the two remaining ships will necessary collide.
The picture on the left is not valid for the situation, because if the two ships have collided in the distant past, then their journey must end at their third collisions, and consequently all four ships have been destroyed when that picture is drawn. (Confusingly explained, but I'm sure you'll get the point.)