Скрыть решение
Решение
Доказательство проводится по индукции. При числе участников, равном 2,
утверждение очевидно. Пусть мы можем расположить
k участников так, как
этого требует условие задачи: а
1, а
2, ...,
ak. Возьмём
(
k +
l ) -гo участника и посмотрим, как он сыграл с
a1. Если он выиграл
или сыграл вничью, то ставим его в начало строки; в противном случае
сравниваем с игроком
a2, и так до тех пор, пока не обнаружим такого
участника из числа а
1, а
2, ...,
ak у которого он выиграл или
сыграл вничью (а предыдущему проиграл). Найдя такого участника, мы поставим
(
k + 1) -го участника перед ним. Если же (
k + 1)-й участник проиграл
всем шахматистам а
1, а
2, ...,
ak, то ставим его в конец
цепочки.