Maths Olympiad Prep

Library / /136 of 397

Combinatorics Difficulty 5.5 AIME, harder Prove it Taiwan

There is a table made up of m×mm \times m unit squares, and at the center points of certain unit squares there is an ant. Starting from time 00, each ant moves forward at speed 11 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 9090^\circ, and then continue forward at speed 11;
(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 9090^\circ, while ants meeting head-on in the east-west direction will turn counterclockwise by 9090^\circ. 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 (0,0)(0,0) represent the SW corner of the table, and coordinate (m,m)(m, m) represent the NE corner of the table. At time tt,
the region {(x,y)x+y1+t}\{(x, y) \mid x + y \le 1 + t\} has no (NE class) ants
the region {(x,y)x+y2m1t}\{(x, y) \mid x + y \ge 2m - 1 - t\} has no (SW class) ants

So at t=m1t = m - 1, this is the last time at which ants can meet, and they can only meet on the line x+y=mx + y = m; after this, all ants only move forward. On the line x+y=mx + y = m, ants moving respectively toward the east, south, west, and north directions will, at most, take m/2m/2 units of time to reach the edge of the table; so altogether we obtain 3m/213m/2 - 1 as an upper bound for doomsday.

Doomsday can indeed occur at time 3m/213m/2 - 1: ant A is located at (1/2,1/2)(1/2, 1/2) moving north, ant B is located at (1/2,m1/2)(1/2, m-1/2) moving south. At time (m1)/2(m-1)/2 they meet at coordinate (1/2,m/2)(1/2, m/2), after which A continues moving east for m1/2m-1/2 units of time, arriving at the edge of the table. At time 3m/213m/2 - 1 the ants' doomsday occurs!

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.