Maths Olympiad Prep

Library / /157 of 158

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Estonia

On an m×mm \times m board, at the midpoints of the unit squares there are some ants. At the time 00 each ant starts moving with speed 11 parallel to some edge of the board until it meets an ant moving in the opposite direction or until it reaches the edge of the board. When two ants moving in the opposite direction meet each other, both turn 9090^\circ clockwise and continue moving parallel to another edge of the board. Upon reaching the edge of the board the ant falls off the board.

a) Prove that eventually all the ants will have fallen off the board.

b) Find the latest possible moment for the last ant to fall off the board.

Solutions — 2

Solution 1

Let the lower left corner of the board be the origin. Divide the units of time and space by 22; then the squares are of dimensions 2×22 \times 2, the coordinates of the midpoints of the squares are odd positive integers, and the speed of the ants is still 11.

We prove by induction that at integer time moments the coordinates of the ants are integers and the sum of the coordinates for any fixed ant has the same parity as the time moment. In addition, the ants can meet only at integer time moments. At time t=0t=0 all coordinates of the ants are odd, so their sum is even. Suppose that at an integer time moment t=kt=k the coordinates of the ants are integers and the sum of the coordinates for any fixed ant has the same parity as the time moment. If two of the ants were to meet each other within the next time unit, they have to move toward each other from time t=kt=k, hence one of their coordinates must be the same. Since the parity of the sum of their coordinates was the same at time t=kt=k, another of their coordinates had to differ by at least 22. Hence they cannot meet before time t=k+1t=k+1. Between time moments t=kt=k and t=k+1t=k+1 every ant has changed only one of its coordinates by 11, hence at time t=k+1t=k+1 the parity of the sum of the coordinates is again the same as the parity of the time moment.

Next we will prove by induction that for any point with integer coordinates (x,y)(x, y) there are no collisions at this point after the time moment t=x+y2t = x + y - 2. For x=y=1x = y = 1 this is obviously true, since there are no collisions in the middle of the lower left square (otherwise one of the ants has to arrive to this point from the edge of the board). Let (x,y)(x, y) be arbitrary and suppose that the claim holds for all points with the sum of the coordinates less than x+yx + y. Suppose that a collision takes place at point (x,y)(x, y) at time tt. One of the participants had to arrive from a point, where one of the coordinates was smaller; w.l.o.g. we can assume that this was the xx-coordinate. If this ant has not collided with anyone before, then tx1x+y2t \le x - 1 \le x + y - 2. If the last collision of this ant occurred at time t<tt' < t, then the coordinates of the last collision were (x(tt),y)(x - (t - t'), y). By the induction assumption tx(tt)+y2t' \le x - (t - t') + y - 2, hence tx+y2t \le x + y - 2.

By symmetry the claim holds when another corner is chosen as the origin. Let the last collision of a particular ant occur at the point (x,y)(x, y), where the coordinates are taken with respect to the nearest corner. W.l.o.g., we can assume xyx \le y. The time from the last collision to the falling off the edge of the ants participating in the collision is at most 2mx2m - x, hence the time elapsed from the start is at most x+y2+2mx3m2x + y - 2 + 2m - x \le 3m - 2. By this time all ants have fallen off the edge. With respect to the original units the maximal time is 32m1\frac{3}{2}m - 1.

For any mm the maximal time can be achieved, if in the beginning there are 22 ants at the adjoining corners of the board moving toward each other. At the moment t=m12t = \frac{m-1}{2} the pair collides and one of the ants starts moving toward the center, falling off the board at time t=32m1t = \frac{3}{2}m - 1.

Solution 2

Part a) can also be solved as follows. For each ant consider the distance to the edge in the direction of its motion. After an ant falls this distance will remain 00. Observe that as long as an ant moves without collision, this distance decreases with speed 11.

Consider now the sum of all such distances. When a collision happens, the sum of the distances of the two corresponding ants is mm, both right before and right after the collision. Thus as long as there are ants left on the board, the total sum decreases with the speed of at least 11. Since in the beginning this sum is a finite number, after some time this sum will become 00 and thus all ants will have fallen off the board.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.