Условие

В соревнованиях по n-борью участвуют 2n человек. Для каждого спортсмена известна его сила в каждом из видов программы. Соревнования проходят следующим образом: сначала все спортсмены участвуют в первом виде программы и лучшая половина из них выходит в следующий круг. Эта половина принимает участие в следующем виде и половина из них выходит в следующий круг, и т.д., пока в n-м виде программы не будет определен победитель. Назовем спортсмена "возможным победителем", если можно так расставить виды спорта в программе, что он станет победителем.

а) докажите, что может так случиться, что хотя бы половина спортсменов является "возможными победителями";
б) докажите, что всегда число "возможных победителей" не превосходит 2n-n;
в) докажите, что может так случиться, что "возможных победителей" ровно 2n-n.


Показать решение