|
|
 |
Условие
В турнире собираются принять участие 25 шахматистов. Все они играют в разную
силу, и при встрече всегда побеждает сильнейший.
Какое наименьшее число партий требуется, чтобы определить двух сильнейших игроков?
Решение
Пример. Устроим турнир по олимпийской системе в пять туров: сначала сыграют 12 пар, потом 6, потом 3. Останется четыре человека, сыграют две пары, а потом победители между собой. Тем самым определится сильнейший. Он сыграл не более пяти партий.
Так как выбыло 24 человека, было сыграно ровно 24 партии. Из пяти (или менее) участников, проигравших сильнейшему, снова по олимпийской системе выделим сильнейшего. На это потребуется не более четырёх партий. Итак, 28 партий достаточно.
Оценка. Проведём турнир по какой-то схеме, позволяющей определить двух сильнейших. Ясно, что все участники, кроме самого сильного, проиграли хотя бы по одной партии (иначе сильнейшего определить нельзя).
Можно считать, что все партии играются последовательно. На каждом шаге работы алгоритма будем называть лидером участника, который пока никому не проиграл. Пусть выполнены условия:
(1) при игре лидера с не лидером всегда выигрывает лидер;
(2) при сравнении двух лидеров выигрывает тот, у кого было больше выигрышей (если выигрышей было поровну, то результат произвольный.
Такие исходы партий возможны потому, что на лидера нет никаких ограничений сверху: если его силу увеличить, то результаты предыдущих партий не изменятся.
Введём понятие подчинения лидеру. Первоначально все участники подчинены только самим себе. После партии типа (2) проигравший и все его подчинённые переподчиняются новому лидеру.
Покажем индукцией по k, что если лидер выиграл k партий, то ему подчинено (вместе с ним самим) не более 2k участников. При k = 0 лидеру подчинён только он сам.
Пусть лидер, выигравший k партий, выигрывает у кого-то в очередной раз. Тот, у кого он выиграл, выиграл не более k партий. Поэтому как выигравшему, так и проигравшему, подчинено не более 2k участников; при объединении этих двух групп получается не более 2k+1 шахматистов.
Итак, при таком течении турнира сильнейший участник выиграл не менее пяти партий, поскольку ему в итоге будут подчинены 25 > 24 участников. Среди пяти шахматистов, проигравших сильнейшему, есть только один, который больше никому не проиграл (иначе мы не будем знать второго по силе участника). Каждый из четырёх остальных проиграл не менее двух партий. Следовательно, всего было не менее 24 + 4 = 28 проигрышей, а значит, было сыграно не менее 28 партий.
Ответ
28 партий.
Замечания
Аналогично можно доказать, что для определения двух сильнейших из n участников надо провести n + m – 2 партии, где целое число m определяется неравенствами m – 1 < log2n ≤ m.
