Этюды для программистов | страница 26

, в котором все соперники играют друг с другом ровно один раз. В предположении отсутствия срывов сильнейший соперник выиграет 2^>n − 1 встреч и проиграет 0, второй по силе соответственно 2^>n — 2 и 1 (уступит лишь сильнейшему), …, а самый слабый — 0 и 2^>n − 1 (проиграет всем). Трудность в том, что в круговом турнире нужно провести 2^>n−1(2^>n − 1) встреч, в то время как в турнире с немедленным выбыванием лишь 2^>n − 1.

Оказавшись между двумя крайностями, выберем компромиссное решение — швейцарскую систему. В первом круге соперник, «посеянный» первым, встречается с последним, второй — с предпоследним и т. д. После каждого круга соперники упорядочиваются в соответствии с набранными очками. Внутри каждой группы (с равным количеством очков) соперники упорядочиваются по среднему числу очков у побежденных ими противников (тем самым ничья не учитывается). В следующем круге соперник, стоящий в описанной классификации на первом месте, встречается с соперником, занимающим наиболее высокое место из тех, с кем он еще не играл. Остальные пары определяются аналогичным образом: соперники должны иметь почти равное количество очков, причем повторные встречи не допускаются. В табл. 5.1 показан возможный трехкруговой турнир по швейцарской системе с восемью участниками. Крупный шахматный деятель Харкнесс утверждает, что турнир по швейцарской системе в

кругов, где N — число игроков, правильно расставит k + 1 первых игроков (и, из соображений симметрии, k + 1 последних игроков). Швейцарская система справедливее немедленного выбывания и гораздо быстрее круговой. Она позволяет всем соперникам играть в каждом круге. Вопрос состоит в том, как ведут себя подобные турниры в условиях реальных соревнований. Предположим, имеется 2^>n соперников. Соперник 1 — сильнейший, соперник 2 — второй по силе, …, соперник 2^>n — слабейший. Для начала проведем круговой турнир, записывая результаты каждого матча. Если встречаются соперники i и j, i < j, положим вероятность победы игрока i равной

1/2 + (j − i)/2^>n+1.

Тем самым более сильный соперник побеждает с вероятностью, превышающей половину. Упорядочим соперников в соответствии с набранным в круговом турнире количеством очков. Внутри каждой группы команд с равным количеством очков упорядочим их по среднему числу очков, набранных побежденными ими соперниками. Если и здесь наблюдаются совпадения, соперники упорядочиваются по исходным номерам. В результате получается круговая классификация