|
|
 |
Условие
Семь лыжников с номерами 1, 2, ... , 7 ушли со старта по очереди и прошли дистанцию – каждый со своей постоянной скоростью. Оказалось, что каждый лыжник ровно дважды участвовал в обгонах. (В каждом обгоне участвуют ровно два лыжника – тот, кто обгоняет, и тот, кого обгоняют.) По окончании забега должен быть составлен протокол, состоящий из номеров лыжников в порядке финиширования. Докажите, что в забеге с описанными свойствами может получиться не более двух различных протоколов.
Решение
Так как скорости постоянны, каждые два лыжника встречались не более одного раза. Будем обозначать лыжников их стартовыми номерами. Победителя никто не мог обогнать, значит, он сам обогнал двоих. Поэтому он – 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.
Замечания
Оба этих случая возможны (в задаче доказывать это не требовалось); соответствующие графики движения приведены на рисунках 1 и 2.
