Maths Olympiad Prep

Library / /25 of 44

Combinatorics Difficulty 6.1 National olympiad Prove it Russia

Seven skiers, numbered from 11 to 77, 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,,71, 2, \ldots, 7 ушли со старта по очереди и прошли дистанцию — каждый со своей постоянной скоростью. Оказалось, что каждый лыжник ровно дважды участвовал в обгонах. (В каждом обгоне участвуют ровно два лыжника — тот, кто обгоняет, и тот, кого обгоняют.) По окончании забега должен быть составлен протокол, состоящий из номеров лыжников в порядке финиширования. Докажите, что в забеге с описанными свойствами может получиться не более двух различных протоколов.

Solution

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

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.