There is a table made up of unit squares, and at the center points of certain unit squares there is an ant. Starting from time , each ant moves forward at speed along a direction parallel to the sides of the squares. During the process, if ants meet:
(i) if two ants meet head-on, they will together turn clockwise by , and then continue forward at speed ;
(ii) if two ants meet perpendicularly, or more than two ants meet, they will continue forward at their original speed and direction.
When an ant crawls to the edge of the table, it falls off the table and never returns. When the last ant falls off the table, we call that moment the "doomsday" of this group of ants.
Considering all possible starting positions of the ants, find the latest possible time at which doomsday occurs, or prove that doomsday does not necessarily occur.
Solution
The rule in (i) can be modified as follows: ants meeting head-on in the north-south direction will turn clockwise by , while ants meeting head-on in the east-west direction will turn counterclockwise by . Comparing before and after this modification, the positions of all ants at any given time do not change; only the roles of the ants that previously met in the east-west direction are swapped between each other, so this does not affect the time at which doomsday occurs. After the modification, all ants are divided into two classes: (NE class) always moving east or north; (SW class) always moving west or south.
Let coordinate represent the SW corner of the table, and coordinate represent the NE corner of the table. At time ,
the region has no (NE class) ants
the region has no (SW class) ants
So at , this is the last time at which ants can meet, and they can only meet on the line ; after this, all ants only move forward. On the line , ants moving respectively toward the east, south, west, and north directions will, at most, take units of time to reach the edge of the table; so altogether we obtain as an upper bound for doomsday.
Doomsday can indeed occur at time : ant A is located at moving north, ant B is located at moving south. At time they meet at coordinate , after which A continues moving east for units of time, arriving at the edge of the table. At time the ants' doomsday occurs!