Library / /28 of 32

, 2010

Combinatorics Difficulty 6.6 National Olympiad Prove it Estonia

In a coordinate city there are $n \ge 3$ tramlines parallel to the $x$ -axis such that each line begins from $x$ -coordinate $0$ and ends at $x$ -coordinate $n$ . Exactly one tram of length $1$ is moving on each line: on the first line with speed $1$ , on the second line with speed $2$ etc, until on the last line with the speed $n$ . When a tram reaches the end of its line it instantly starts moving back without turning around. In the morning all trams start moving at the same time from the starting position where the $x$ -coordinate of the back end of the tram is $0$ . Prove that the trams' projections onto the $x$ -axis never cover the whole interval from $0$ to $n$ . (Grade 12.)

Solution

The projections of the trams can cover the whole interval only when one projection covers $[0, 1]$ , another $[1, 2]$ etc. until $[n-1, n]$ . Consider the moments when the projection of the slowest tram covers one of these intervals. When the slowest tram moves by $1$ unit, then the fastest and the third fastest trams move correspondingly by $n$ and $n-2$ units. Together these two trams move by $2n-2$ units which is exactly one to and fro cycle.

Denote the integer positions of the trams on the round trip by numbers $0$ to $2n-3$ , i.e. the starting position is $0$ and each next one until returning to the starting point is greater by one. Call these numbers the position characteristics. If the sum of the position characteristics of two trams is $2n - 2$ , then their projections cover the same interval because one of them has moved the same amount from the starting point as the other one still has to go to reach it. If the sum of the position characteristics is $0$ , then they both are in the starting positions, so they again cover the same interval. Hence, when the sum of the position characteristics is divisible by $2n - 2$ , the projections cover the same interval.

At the beginning the sum of the position characteristics of the fastest and the third fastest tram is $0$ and each time they together move by $2n - 2$ units the sum of their position characteristics stays divisible by $2n - 2$ . Consequently, when the projection of the slowest tram covers an interval with integer endpoints, the projections of these two trams cover the same interval, hence at least one of the intervals is not covered.

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.