IMO 1988 SL 29

Origin: USA

Problem

A number of signal lights are equally spaced along a one-way railroad track, labeled in order 1, 2, . . ., N (N \geq2). As a safety rule, a train is not allowed to pass a signal if any other train is in motion on the length of track between it and the following signal. However, there is no limit to the number of trains that can be parked motionless at a signal, one behind the other. (Assume that the trains have zero length.) A series of K freight trains must be driven from Signal 1 to Signal N. Each train travels at a distinct but constant speed (i.e., the speed is fixed and different from that of each of the other trains) at all times when it is not blocked by the safety rule. Show that regardless of the order in which the trains are arranged, the same time will elapse between the first train’s departure from Signal 1 and the last train’s arrival at Signal N.

Solution

Let the first train start from Signal 1 at time 0, and let tj be the time it takes for the jth train in the series to travel from one signal to the next. By induction on k, we show that Train k arrives at signal n at time sk + (n −2)mk, where sk = t1 + \cdot \cdot \cdot + tk and mk = maxj=1,...,k tj. For k = 1 the statement is clear. We now suppose that it is true for k trains and for every n, and add a (k + 1)th train behind the others at Signal 1. There are two cases to consider: (i) tk+1 \geqmk, i.e., mk+1 = tk+1. Then Train k + 1 leaves Signal 1 when all the others reach Signal 2, which by the induction happens at time sk. Since by the induction hypothesis Train k arrives at Signal i+1 at time sk+(i−1)mk \leqsk+(i−1)tk+1, Train k+1 is never forced to stop. The journey finishes at time sk + (n −1)tk+1 = sk+1 + (n −2)mk+1. (ii) tk+1 < mk, i.e., mk+1 = mk. Train k + 1 leaves Signal 1 at time sk, and reaches Signal 2 at time sk + tk+1, but must wait there until all the other trains get to Signal 3, i.e., until time sk + mk (by the induction hypothesis). So it reaches Signal 3 only at time sk + mk + tk+1. Similarly, it gets to Signal 4 at time sk + 2mk + tk+1, etc. Thus the entire schedule finishes at time sk + (n −2)mk + tk+1 = sk+1 + (n −2)mk+1.