Saturday, September 12, 2009

The 8 ants problem

Here's the solution to the 8 ants problem:

Let all ants have different velocities. Since each ant is moving with some constant velocity, the relative velocity between any two ants (V1-V2) will always be constant. Constant velocity means straight line displacement. Hence,

(1) Relative displacement of any ant with respect to any other ant will be a straight ine.

Meaning, if ant A1 looks at ant A3, it will see A3 as moving in a straight line (relative to A1). Now, let A1 and A2 be those ants about which it is given that they meet all others. Let us see from the frame of reference of A1 (A1 is stationary at origin in this frame). A1 will see all ants moving at different velocities along straight lines. But since A1 meets all ants at least once,

(2) The straight line paths of all ants must pass through the origin.

Also, it is true that:
(3) Two straight lines can intersect only once.

Now we know that the locus of all ants are straight lines passing through the origin. Also, if any ant has to meet any other ant, it can do so only at the origin (by (3)). Now, since ant A2 meets all other ants, we can be sure that the meeting happens only at the origin. It is only possible if all the ants reach the origin at the same time. I means that each ant meets every other ant at origin. Hence Proved.

Now, there is a small issue. Not with the solution, but with the problem itself. It is not valid when all the ants are moving in one straight line. (because then, postulate 3 won't hold). I can give you one simple example to show that. Suppose A2 ... A8 are moving in the same direction in a straight line. V2>V3=V4=V5=V6=V7=V8. A2 is lagging all others at this point in time. And A1 is moving in the opposite direction towards all others. Hence, A1 will meet all ants. Also, A2 will meet all ants, as its velocity is greater than all others. But V3..V8 will never meet as they are moving with the same speed along the same line. Hence all ants do not meet.

No comments: