|
|
 |
Условие
В соревнованиях по n-борью участвуют 2n человек. Для
каждого спортсмена известна его сила в каждом из видов программы. Соревнования
проходят следующим образом: сначала все спортсмены участвуют в первом виде
программы и лучшая половина из них выходит в следующий круг. Эта половина
принимает участие в следующем виде и половина из них выходит в следующий круг,
и т.д., пока в n-м виде программы не будет определен победитель. Назовем
спортсмена возможным победителем, если можно так расставить виды спорта в программе, что он станет победителем.
а) Докажите, что может так случиться, что хотя бы половина спортсменов является возможными победителями.
б) Докажите, что число возможных победителей не превосходит 2n – n.
в) Докажите, что может так случиться, что возможных
победителей ровно 2n – n.
Решение
а) Индукция по n. База очевидна: один победитель единственного соревнования из двоих – это уже половина.
Пусть есть пример n соревнований для 2n спортсменов с 2n–1 возможными победителями. Разделим 2n+1 спортсменов на две равные группы A и A'. Будем считать, что в некотором виде соревнований a каждый спортсмен из A' сильнее всех из A, а в остальных видах – наоборот. Если первым соревнованием провести a, то останется группа A', если любое другое – останется группа A. Применяя индуктивное предположение к группам A и A' по отдельности, получаем пример с 2n–1 + 2n–1 = 2n возможными победителями.
б) Укажем для каждого вида соревнований спортсмена, который при любом порядке проведения соревнований выбывает в этом виде или раньше. Построение индуктивное.
Для 1-го вида соревнований – это самый слабый в этом виде.
Пусть уже построено такое множество Ak = {a1, ..., ak} спортсменов, что ai выбывает в i-м виде соревнований или раньше.
Обозначим через ak+1 спортсмена, который в (k+1)-м виде слабее всех, не входящих в Ak. Докажем, что ak+1 выбывает в (k+1)-м виде соревнования или раньше при любом порядке соревнований. Пусть (k+1)-й вид соревнований проходит r-м по порядку, а из множества Ak за первые r – 1 соревнований выбыло w человек.
После (k+1)-го вида соревнований должно пройти по крайней мере k – w соревнований с номерами 1, ..., k. Поэтому k – w ≤ n – r < 2n–r.
В r-м по порядку виде соревнований выбывает 2n–r > k – w человек. Поэтому ak+1 (если он не выбыл раньше) не проходит в следующее соревнование.
в) Докажем по индукции, что для всех n ≥ 1
существует такой пример n + 1 соревнований с 2n участниками, что, выбирая n соревнований и порядок их проведения, можно сделать победителями 2n – 1 участников, а единственному исключительному участнику (будем называть его аутсайдером) можно обеспечить выход в финал.
База при n = 1 очевидна.
Шаг индукции. Строим пример n + 2 соревнований с 2n+1 участниками. Опять разделим спортсменов на равные две группы B и B'. Будем считать, что в некотором виде соревнований b любой из B' сильнее любого из B, а в остальных видах – наоборот. Каждая из групп по отдельности в видах соревнований, отличных от b, даёт пример выполнения доказываемого утверждения. Дополнительно предположим, что аутсайдер в B – самый сильный среди B в виде b.
Проводя первым b, получим 2n – 1 возможных победителей из B', причём при некотором порядке аутсайдер из B' выйдет в финал по индуктивному предположению.
Если вообще не проводить b, то в первом соревновании выбывают все из B', а далее проводится n – 1 соревнование. По индуктивному предположению, выбором первого соревнования и порядка проведения остальных можно сделать победителями 2n – 1 спортсменов из B.
Осталось объяснить, как сделать победителем аутсайдера в B. Для этого первым проводим тот вид соревнований, который является финальным при порядке, обеспечивающем выход аутсайдера в финал. После этого останутся только спортсмены из B. Далее проводим соревнования в таком порядке, который обеспечивает выход аутсайдера из B в финал, а завершаем – соревнованием b. В нём аутсайдер побеждает по построению примера.
Теперь повторим рассуждение из а), используя при индуктивном переходе более точную оценку, доказанную выше. База индукции по-прежнему очевидна. В индуктивном переходе заметим, что из группы A' победителями можно сделать 2n – n человек, а из A – 2n – 1 человека. Итого получаем
2n – n + 2n – 1 = 2n+1 – (n + 1) возможных победителей.
