Track / Stage 6 / 138 of 400 #1138 of 1964

Problem 1138

National Olympiad, first round

Combinatorics Difficulty 6.1 Prove it Russia — Regional Round · Russia

Seven skiers, numbered from $1$ to $7$ , 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). It happened that each skier participated in an overtaking exactly two times (in each overtaking, exactly two skiers participated: the one who overtakes and the one who is overtaken.)
After the race was finished, the list of ranks is published (that list contains the numbers of skiers in the order they finished the race). Prove that all the conditions being satisfied, not more than two possible lists might appear.

Семь лыжников с номерами $1, 2, \ldots, 7$ ушли со старта по очереди и прошли дистанцию — каждый со своей постоянной скоростью. Оказалось, что каждый лыжник ровно дважды участвовал в обгонах. (В каждом обгоне участвуют ровно два лыжника — тот, кто обгоняет, и тот, кого обгоняют.) По окончании забега должен быть составлен протокол, состоящий из номеров лыжников в порядке финиширования. Докажите, что в забеге с описанными свойствами может получиться не более двух различных протоколов.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Заметим, что чётность места каждого лыжника менялась при любом обгоне; значит, его место на финише — той же чётности, что и на старте.
Так как скорости постоянны, каждые два лыжника встречались не более одного раза. Будем обозначать лыжников их стартовыми номерами.
Победителя никто не мог обогнать, значит, он сам обогнал двоих. Поэтому он — $3$ , и обогнал лыжников $1$ и $2$ . Аналогично, финишировавший последним не мог никого обогнать, поэтому его обогнали двое, он — $5$ , и его обогнали $6$ и $7$ . Далее, лыжник $1$ не мог никого обогнать, то есть он финишировал третьим (и его, кроме $3$ , обогнал лыжник, финишировавший вторым), а лыжника $7$ никто не мог обогнать, и он финишировал пятым (обогнав $5$ и лыжника, финишировавшего шестым).
Итак, осталось выяснить, какими финишировали лыжники с чётными номерами. Вторым финишировать мог либо $2$ , либо $4$ . Если $2$ пришел вторым, то он обогнал $1$ , и с группой лидеров ( $1$ , $2$ , $3$ ) больше обгонов не происходило. Значит, лыжника $4$ могли только обгонять, он на финише шестой, а лыжник $6$ — четвёртый.
Если же вторым пришел $4$ , то $2$ мог придти к финишу только четвёртым (значит, $4$ обогнал $2$ и $1$ ), а шестым пришел $6$ (обогнав $5$ и уступив $7$ ). Итого, возможны только два протокола: $3, 2, 1, 6, 7, 4, 5$ и $3, 4, 1, 2, 7, 6, 5$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.