Nine skiers participated in a race. They started one by one, and each skier passed the distance with a constant speed (which could be different for different skiers). Determine if it could happen that each skier participated in an overtaking exactly four times. (In each overtaking, exactly two skiers participated: the one who overtakes and the one who is overtaken.)
Девять лыжников ушли со старта по очереди и прошли дистанцию — каждый со своей постоянной скоростью. Могло ли оказаться, что каждый лыжник участвовал ровно в четырёх обгонах? (В каждом обгоне участвуют ровно два лыжника — тот, кто обгоняет, и тот, кого обгоняют.)
Solution
It could not happen.
Suppose it is possible. Since the speeds are constant, any two skiers met at most once. Then the skier who started first could not overtake anyone; therefore, he was overtaken by four skiers and finished fifth. On the other hand, the skier who started last could not be overtaken by anyone, so he himself overtook four skiers and also finished fifth. Contradiction.
Note. A similar argument shows that only skier number 5 could have finished both first and last in the race.
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 and solution reproduced as published; topic and difficulty added by this site.