Всесиб 2026, отборочный этап, 10 класс, задача 5
( баллов) В шахматном турнире, который проводился в классе с учащимися, каждая пара учеников сыграла максимум одну партию друг с другом. После окончания турнира оказалось, что, для любой сыгранной партии, по крайней мере один из её участников до начала этой партии сыграл не более партий. Каково максимально возможное количество сыгранных партий на этом турнире?
Ответ
Ответ. .
Решение. Докажем, что количество сыгранных на турнире партий не превосходит . Рассмотрим последнюю сыгранную на турнире партию, один из её участников сыграл к моменту её начала не больше партий, значит всего в турнире он сыграл не больше партий. Теперь исключим его и все сыгранные с его участием партии из турнира и рассмотрим оставшихся ученика и все сыгранные между ними партии. Количество сыгранных в любой момент партий у каждого оставшегося ученика не увеличится, по сравнению с исходным турниром. Следовательно, для этого нового турнира справедливо исходное условие — для любой сыгранной в нём партии, по крайней мере один из её участников к этому моменту сыграл не более партий. Повторим для учеников и нового турнира то же рассуждение — выберем последнюю сыгранную в нём партию, одного из её участников, сыгравшего в нём к моменту её начала не больше партий, а всего в новом турнире не больше партий, и исключим его и сыгранные им партий, получим турнир уже для участников, и так далее. Так сделаем раз, пока не получим турнир для участников. В нём с соблюдением условий могут быть сыграны все возможные партий. Таким образом, общее количество сыгранных на турнире партий не превосходит .
Пример, когда сыгранных на турнире партий ровно , легко строится «обратным ходом» по доказательству оценки. Первых учеников заставляем сыграть все партий между собой, потом раз добавляем по одному ученику, заставляя его тут же сразу последовательно сыграть партий с некоторыми учениками (неважно, какими именно), участвовавших в турнире до его там появления. Получим в точности сыгранных партий.