шахматный турнир
12.03.2001 22:02 |
МЦНМО
В шахматном турнире каждый участник сыграл с каждым по партии.
Докажите, что участников можно занумеровать так, что ни один из
них не проиграл непосредственно следующему за ним.
Хочу подсказку
Решение:
Если в турнире были ничьи, то их можно заменить на победы одного
из участников, при этом задача нумерации участников не упростится;
поэтому достаточно решить задачу в случае турнира без ничей.
Применим индукцию по числу n участников
турнира. Случай турнира из двух участников очевиден.
Пусть для n=k утверждение задачи верно.
Рассмотрим некоторый турнир без ничьих с k+1 участниками.
Выделим одного из участников - C, все встречи между остальными
участниками образуют турнир для k участников.
Согласно предположению индукции, этих k участников можно
обозначить A1,A2,...,Ak
так, что участник Ai выиграл у Ai+1 (для всех
i=1,2,...,k-1).
Пусть m - наибольший номер, такой что участник С проиграл
участникам A1,A2,...,Am (если C
выиграл у
участника A1, то полагаем m=0).
Тогда C выиграл у участника Am+1 (кроме случая m=k).
Поэтому в ряду
A1,A2,...,Am,C,Am+1,Am+2,...,Ak
каждый участник выиграл у следующего
(если m=0, то ряд начинается с С, если m=k, то ряд заканчивается на
C). Нумеруя участников по порядку в указанном выше ряду, получим
требуемую нумерацию.
Написать комментарий
|
