|
В квалификационном турнире n шахматистов играют в один круг. Для попадания в основной турнир необходимо занять место не ниже m-го. При равенстве очков преимущество имеет спортсмен с большим рейтингом (рейтинг у всех разный). Каково минимальное количество очков, гарантирующее шахматисту попадание в основной турнир независимо от результатов других игр и рейтинга? (За победу в шахматах дают 1 очко, за ничью - полочка, за поражение - 0). задан 22 Мар '14 21:17 
serg55 |
|
Случай $%m=n$% не представляет интереса, так как при этом все проходят, и достаточно набрать 0 очков. Поэтому далее считаем, что $%m < n$%. Рассмотрим такую ситуацию, когда $%m+1$% участник сыграл вничью друг с другом и выиграл у всех остальных. Каждый при этом набирает $%(n-m-1)+m/2$% очков, и для выхода в основной турнир этого числа очков не будет достаточно, так как можно оказаться при этом $%(m+1)$%-м по счёту, обладая самым низким рейтингом. Покажем, что если добавить половину очка, то есть набрать не менее $%n-(m+1)/2$% очков, то этого гарантированно хватит. Если игрок с таким количеством очков займёт место ниже $%m$%-го, то каждый обладатель места с 1-го по $%m$%-е включительно наберёт как минимум столько же очков. И тогда получится, что $%m+1$% игрок в сумме набрал не менее $%(m+1)(n-(m+1)/2)$% очков. Покажем, что так быть не может. При играх между собой эти участники играют $%m(m+1)/2$% матчей, разыгрывая столько же очков. Оставшееся число матчей равно $%(m+1)(n-(m+1))$%, и общее количество набранных очков не превосходит этого количества. В сумме выходит не более $%(m+1)(n-(m+2)/2)$%, что меньше указанного выше количества. отвечен 22 Мар '14 22:06 
falcao |