Maths Olympiad Prep

Library / /5 of 6

Geometry Difficulty 8.9 Shortlist Prove it Vietnam

There are 4444 distinct holes on a line and 20172017 ants. Each ant crawled up from a hole, then moved to another hole and crawled down. Denote TT as the set of time points that the ants crawled up or crawled down from some hole. Suppose that the speed of the ants are pairwise distinct and they did not change their own speed. Prove that if T45|T| \le 45 then there exist two ants did not meet.

Note that two ants met when there exists a time point such that they were at the same location on the line, including the holes.

Solution

We call a time point "special" if at the time, there some ant crawled up/down from the hole. It is easy to see that we just need to solve the problem in case T=45|T| = 45 (if T<45|T| < 45, we consider some more special time points and that will make the below argument stronger).

Consider the system of coordination Oxy in which Ox expresses to the location of holes on the line and Oy expresses to the time. The coordination of holes are x1,x2,,x44x_1, x_2, \dots, x_{44} and special times are y1,y2,,y45y_1, y_2, \dots, y_{45}.

An ant move from point (xa,yb)(x_a, y_b) to point (xc,yd)(x_c, y_d) if this ant crawled from the hole xax_a at the time yby_b and move to the hole xcx_c at the time ydy_d. Since that speed of ant did not change, the graph express for that moving is a segment connect two correspondent points.

Thus in total, we have 20172017 segments and since the speed of ants are pairwise distinct, the lines have different directions. To finish the problem, we need to show that at least two segment among them does not intersect. Note that the number of end points of these segment is no more than 4544=1980<201745 \cdot 44 = 1980 < 2017 then we will prove the generalization version of this problem as: If there are nn points on the plane, then there are no more than nn segments connect them such that no two segments parallel or overlap.

(*)

We shall prove (*) by induction. It is easy to check for n=2,3n = 2, 3.

For n4n \ge 4, suppose that the argument is true for n1n-1 points. We consider two cases:

1. If among nn points, there is one point is the end point of at most one segment, then by removing it (also the segment has it as the end point), we come to the case of n1n-1 points.

2. If each point is the end point of at least two segments, then we will show that the number of segments is exactly the same as the number of points. Indeed, if there is some point is the end point of three segments, for example point AA is the end point of AB,AC,ADAB, AC, AD. If point AA lies inside triangle BCDBCD then the second segment from BB cannot cut both ACAC and ADAD. Otherwise, we can suppose that the ray ACAC lie between two rays AB,ADAB, AD then the second segment from CC cannot cut both ABAB and ADAD. This implies that each point is the end point of exactly two segments then the number of segment is nn.

Hence (*) also holds for nn which complete the proof. ■

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.