Разделы 
Дополнительно
Задача по математике - 3298
2019-06-02 
В соревнованиях по $n$-борью участвуют $2^n$ человек. Для каждого спортсмена известна его сила в каждом из видов программы. Соревнования проходят следующим образом: сначала все спортсмены участвуют в первом виде программы, и лучшая половина из них выходит в следующий круг. Эта половина принимает участие в следующем виде, и половина из них выходит в следующий круг, и т. д., пока в $n$-м виде программы не будет определен победитель. Назовем спортсмена «возможным победителем», если можно так расставить виды спорта в программе, что он станет победителем.
а) докажите, что может так случиться, что хотя бы половина спортсменов является «возможными победителями»;
б) докажите, что всегда число «возможных победите¬лей» не превосходит $2^n - n$;
в) докажите, что может так случиться, что «возможных победителей» ровно $2^n - n$.
Решение:
Все пункты этой задачи решаются по индукции, причем сложность рассуждений резко растет.
Начнем с решения пункта «а». База индукции очевидна: один победитель единственного соревнования из двоих - это уже половина.
Пусть есть пример $2^n$ спортсменов, упорядоченных по силе в $n$ видах спорта так, что среди них $2^{n-1}$ возможных победителей. Обозначим такой пример $C_n$.
Опишем пример $C_{n+1}$ из $2^{n+1}$ спортсменов, упорядоченных по силе в $n + 1$ виде спорта так, что среди них $2^n$ возможных победителей. Разделим спортсменов на две равные группы $A$ и $A^{ \prime}$. Силы спортсменов определим так, что
1) в видах спорта с 1-го по $n$-й спортсмены в каждой из групп упорядочены, как в примере $C_n$;
2) в $(n + 1)$-м виде спорта любой спортсмен из $A^{ \prime}$ сильнее любого из $A$, а в остальных видах - наоборот;
3) в группе $A$ спортсмены упорядочены по $(n + 1)$-му виду спорта так же, как и по $n$-му (а в группе $A^{ \prime}$ спортсмены упорядочены по $(n + 1)$-му виду спорта произвольным образом).
Если первым провести соревнование по $(n + 1)$-му виду спорта, то останется группа $A^{ \prime}$. По предположению индукции половина спортсменов из этой группы может стать победителями.
Если провести соревнование по $n$-му виду спорта - останется группа $A$. Покажем, что половина спортсменов из этой группы тоже может стать победителями. По предположению индукции, для половины спортсменов из $A$ найдется последовательность соревнований, при которых они становятся победителями. Однако эта последовательность включает $n$-й вид спорта, который мы уже сыграли! Сыграем вместо $n$-го вида спорта $(n + 1)$-й, и воспользуемся тем, что в группе $A$ спортсмены упорядочены по $(n + 1)$-му виду спорта так же, как и по $n$-му. Итак, половина спортсменов из группы $A$ может стать победителями, и половина спортсменов из группы $A^{ \prime}$ может стать победителями. Индуктивный переход доказан.
б) Укажем для каждого вида спорта спортсмена, который при любом порядке проведения соревнований выбывает в этом виде или раньше (независимо от того, каким по очереди проводится этот вид спорта), причем для разных видов мы выберем разных спортсменов. Тогда ни один из них не может стать победителем, и возможных победителей не более, чем $2^n - n$. Построение индуктивное.
База индукции: для 1-го вида соревнований - это самый слабый в 1-м виде.
Шаг индукции: Пусть уже построено множество $A_k = \{ a_1, \cdots, a_k \}$ спортсменов такое, что at выбывает в $i$-м виде спорта или раньше.
Из спортсменов, не входящих в множество $A_k$, выберем самого слабого в $(k + 1)$-м виде спорта, обозначим его через $a_{k+1}$. Докажем, что $a_{k+1}$ выбывает в $(k + 1)$-м виде спорта или раньше при любом порядке соревнований. Пусть $(k + 1)$-й вид спорта проводится $r$-м по порядку, а из множества $A_k$ за первые $r - 1$ соревнований выбыло $w$ человек. В $r$-м соревновании выбывает $2^{n-r}$ человек. Поэтому $a_{k+1}$ может пройти в следующий тур только при выполнении условия $2^{n-r} \leq k - w$ (так как лишь $k - w$ из оставшихся участников могут быть слабее в $(k + 1)$-м виде, чем $a_{k+1}$). Но после $(k + 1)$-го вида спорта должны пройти соревнования по не менее чем $k - w$ видам спорта с номерами из множества ${1, \cdots, k}$ (по предположению индукции). Поэтому $k - w \leq n - r < 2^{n-r}$. Мы воспользовались неравенством $2^l > l$, верным для всех целых чисел. Таким образом, $a_{k+1}$ выбывает в $(k + 1)$-м виде спорта или раньше, и шаг индукции доказан.
в) Лемма. Пусть $2n$ спортсменов соревнуются в $n + 1$ виде спорта. При этом соревнование по $(n + 1)$-му виду спорта проводится обязательно, а из оставшихся видов спорта выбирается n - 1 (соревнование по последнему виду спорта может проводиться любым номером). Тогда может оказаться, что все, кроме одного спортсмена (а именно, кроме самого слабого в $(n + 1)$-м виде спорта), являются возможными победителями.
Прежде чем доказывать лемму, поясним, как использовать ее для решения пункта «в». Обозначим пример из этой леммы через $E_n$. База индукции по-прежнему очевидна. Для индуктивного перехода повторим рассуждение пункта «а» с незначительными изменениями.
Пусть есть пример $2^n$ спортсменов, упорядоченных по силе в $n$ видах спорта так, что среди них $2^n - n$ возможных победителей, обозначим такой пример $D_n$.
Опишем пример $D_{n+1}$ из $2^{n+1}$ спортсменов. Опять разделим спортсменов на две равные группы $A$ и $A^{ \prime}$. Силы спортсменов определим так, что
1) в видах спорта с 1-го по $n$-й спортсмены в группе $A^{ \prime}$ упорядочены, как в примере $D_n$;
2) в $(n + 1)$-м виде спорта любой спортсмен из группы $A^{ \prime}$ сильнее любого из группы $A$, а в остальных видах - наоборот;
3) в группе $A$ спортсмены упорядочены, как в примере $E_n$.
Если первым провести соревнование по $(n + 1)$-му виду спорта, то останется группа $A^{ \prime}$. По предположению индукции $2^n - n$ спортсменов из этой группы могут стать победителями.
Рассмотрим любого спортсмена из группы $A$, который может быть победителем в примере $E_n$. Рассмотрим последовательность соревнований, при которой он становится победителем. Пусть при этом не проводится соревнование по $j$-му виду спорта. Проведем его первым - останется группа $A$. Теперь проведем оставшиеся соревнования в порядке, необходимом, чтобы сделать этого спортсмена победителем в примере $E_n$.
Итак, из группы $A^{ \prime}$ победителями можно сделать $2^n - n$ человек, а из $A$ - $2^n - 1$ человек. Итого получаем $2^n - n + 2^n - 1 = 2^{n+1} - (n + 1)$ возможных победителей.
Доказательство леммы. Докажем более сильное утверждение: Пусть $2^n$ спортсменов соревнуются в $n + 1$ виде спорта. При этом соревнование по $(n + 1)$-му виду спорта проводится обязательно, а из оставшихся видов спорта выбирается $n - 1$ (соревнование по $(n + 1)$-му виду спорта может проводиться любым номером). Тогда может оказаться, что все, кроме одного спортсмена (а именно, кроме самого слабого в $(n + 1)$-м виде спорта), являются возможными победителями, а единственный исключительный участник (будем называть его аутсайдером) может выйти в финал.
База $(n = 1)$ очевидна.
Индуктивный переход. Строим пример $E_{n+1}$, исходя из существования примера $E_n$. Опять разделим $2^{n+1}$ спортсменов на равные группы $B$ и $B^{ \prime}$. Определим их силы так, чтобы в 1-м виде спорта любой из $B^{ \prime}$ был сильнее любого из $B$, в остальных видах - наоборот, а в виде $j$ ($2 \leq j \leq n + 2$) спортсмены внутри каждой из групп $B$ и $B^{ \prime}$ были упорядочены, как спортсмены в примере $E_n$ в виде $j - 1$. Дополнительно потребуем, чтобы аутсайдер в $B$ был самым сильным среди $B$ в 1-м виде спорта.
Проводя сначала соревнования по 1-му виду спорта, получим $2^n - 1$ возможных победителей из $B^{ \prime}$, причем при некотором порядке проведения соревнований аутсайдер из $B^{ \prime}$ выйдет в финал (индуктивное предположение).
Если вообще не проводить соревнования по 1-му виду спорта, то в первом соревновании выбывают все спортсмены из $B^{ \prime}$, а далее проводится $n$ соревнований. По предположению индукции, выбрав вид спорта для первого соревнования и порядок проведения соревнований по остальным видам спорта, можно сделать победителями $2^n - 1$ спортсменов из $B$.
Осталось объяснить, как сделать победителем аутсайдера в $B$. Для этого первым проводим тот вид соревнований, который является последним при порядке соревнований, обеспечивающем выход аутсайдера в финал. После этого останутся только спортсмены из $B$. Далее проводим соревнования в таком порядке, который обеспечивает выход аутсайдера из $B$ в финал, а завершаем - 1-м видом спорта. В нем аутсайдер побеждает.
В соревнованиях по $n$-борью участвуют $2^n$ человек. Для каждого спортсмена известна его сила в каждом из видов программы. Соревнования проходят следующим образом: сначала все спортсмены участвуют в первом виде программы, и лучшая половина из них выходит в следующий круг. Эта половина принимает участие в следующем виде, и половина из них выходит в следующий круг, и т. д., пока в $n$-м виде программы не будет определен победитель. Назовем спортсмена «возможным победителем», если можно так расставить виды спорта в программе, что он станет победителем.
а) докажите, что может так случиться, что хотя бы половина спортсменов является «возможными победителями»;
б) докажите, что всегда число «возможных победите¬лей» не превосходит $2^n - n$;
в) докажите, что может так случиться, что «возможных победителей» ровно $2^n - n$.
Решение:
Все пункты этой задачи решаются по индукции, причем сложность рассуждений резко растет.
Начнем с решения пункта «а». База индукции очевидна: один победитель единственного соревнования из двоих - это уже половина.
Пусть есть пример $2^n$ спортсменов, упорядоченных по силе в $n$ видах спорта так, что среди них $2^{n-1}$ возможных победителей. Обозначим такой пример $C_n$.
Опишем пример $C_{n+1}$ из $2^{n+1}$ спортсменов, упорядоченных по силе в $n + 1$ виде спорта так, что среди них $2^n$ возможных победителей. Разделим спортсменов на две равные группы $A$ и $A^{ \prime}$. Силы спортсменов определим так, что
1) в видах спорта с 1-го по $n$-й спортсмены в каждой из групп упорядочены, как в примере $C_n$;
2) в $(n + 1)$-м виде спорта любой спортсмен из $A^{ \prime}$ сильнее любого из $A$, а в остальных видах - наоборот;
3) в группе $A$ спортсмены упорядочены по $(n + 1)$-му виду спорта так же, как и по $n$-му (а в группе $A^{ \prime}$ спортсмены упорядочены по $(n + 1)$-му виду спорта произвольным образом).
Если первым провести соревнование по $(n + 1)$-му виду спорта, то останется группа $A^{ \prime}$. По предположению индукции половина спортсменов из этой группы может стать победителями.
Если провести соревнование по $n$-му виду спорта - останется группа $A$. Покажем, что половина спортсменов из этой группы тоже может стать победителями. По предположению индукции, для половины спортсменов из $A$ найдется последовательность соревнований, при которых они становятся победителями. Однако эта последовательность включает $n$-й вид спорта, который мы уже сыграли! Сыграем вместо $n$-го вида спорта $(n + 1)$-й, и воспользуемся тем, что в группе $A$ спортсмены упорядочены по $(n + 1)$-му виду спорта так же, как и по $n$-му. Итак, половина спортсменов из группы $A$ может стать победителями, и половина спортсменов из группы $A^{ \prime}$ может стать победителями. Индуктивный переход доказан.
б) Укажем для каждого вида спорта спортсмена, который при любом порядке проведения соревнований выбывает в этом виде или раньше (независимо от того, каким по очереди проводится этот вид спорта), причем для разных видов мы выберем разных спортсменов. Тогда ни один из них не может стать победителем, и возможных победителей не более, чем $2^n - n$. Построение индуктивное.
База индукции: для 1-го вида соревнований - это самый слабый в 1-м виде.
Шаг индукции: Пусть уже построено множество $A_k = \{ a_1, \cdots, a_k \}$ спортсменов такое, что at выбывает в $i$-м виде спорта или раньше.
Из спортсменов, не входящих в множество $A_k$, выберем самого слабого в $(k + 1)$-м виде спорта, обозначим его через $a_{k+1}$. Докажем, что $a_{k+1}$ выбывает в $(k + 1)$-м виде спорта или раньше при любом порядке соревнований. Пусть $(k + 1)$-й вид спорта проводится $r$-м по порядку, а из множества $A_k$ за первые $r - 1$ соревнований выбыло $w$ человек. В $r$-м соревновании выбывает $2^{n-r}$ человек. Поэтому $a_{k+1}$ может пройти в следующий тур только при выполнении условия $2^{n-r} \leq k - w$ (так как лишь $k - w$ из оставшихся участников могут быть слабее в $(k + 1)$-м виде, чем $a_{k+1}$). Но после $(k + 1)$-го вида спорта должны пройти соревнования по не менее чем $k - w$ видам спорта с номерами из множества ${1, \cdots, k}$ (по предположению индукции). Поэтому $k - w \leq n - r < 2^{n-r}$. Мы воспользовались неравенством $2^l > l$, верным для всех целых чисел. Таким образом, $a_{k+1}$ выбывает в $(k + 1)$-м виде спорта или раньше, и шаг индукции доказан.
в) Лемма. Пусть $2n$ спортсменов соревнуются в $n + 1$ виде спорта. При этом соревнование по $(n + 1)$-му виду спорта проводится обязательно, а из оставшихся видов спорта выбирается n - 1 (соревнование по последнему виду спорта может проводиться любым номером). Тогда может оказаться, что все, кроме одного спортсмена (а именно, кроме самого слабого в $(n + 1)$-м виде спорта), являются возможными победителями.
Прежде чем доказывать лемму, поясним, как использовать ее для решения пункта «в». Обозначим пример из этой леммы через $E_n$. База индукции по-прежнему очевидна. Для индуктивного перехода повторим рассуждение пункта «а» с незначительными изменениями.
Пусть есть пример $2^n$ спортсменов, упорядоченных по силе в $n$ видах спорта так, что среди них $2^n - n$ возможных победителей, обозначим такой пример $D_n$.
Опишем пример $D_{n+1}$ из $2^{n+1}$ спортсменов. Опять разделим спортсменов на две равные группы $A$ и $A^{ \prime}$. Силы спортсменов определим так, что
1) в видах спорта с 1-го по $n$-й спортсмены в группе $A^{ \prime}$ упорядочены, как в примере $D_n$;
2) в $(n + 1)$-м виде спорта любой спортсмен из группы $A^{ \prime}$ сильнее любого из группы $A$, а в остальных видах - наоборот;
3) в группе $A$ спортсмены упорядочены, как в примере $E_n$.
Если первым провести соревнование по $(n + 1)$-му виду спорта, то останется группа $A^{ \prime}$. По предположению индукции $2^n - n$ спортсменов из этой группы могут стать победителями.
Рассмотрим любого спортсмена из группы $A$, который может быть победителем в примере $E_n$. Рассмотрим последовательность соревнований, при которой он становится победителем. Пусть при этом не проводится соревнование по $j$-му виду спорта. Проведем его первым - останется группа $A$. Теперь проведем оставшиеся соревнования в порядке, необходимом, чтобы сделать этого спортсмена победителем в примере $E_n$.
Итак, из группы $A^{ \prime}$ победителями можно сделать $2^n - n$ человек, а из $A$ - $2^n - 1$ человек. Итого получаем $2^n - n + 2^n - 1 = 2^{n+1} - (n + 1)$ возможных победителей.
Доказательство леммы. Докажем более сильное утверждение: Пусть $2^n$ спортсменов соревнуются в $n + 1$ виде спорта. При этом соревнование по $(n + 1)$-му виду спорта проводится обязательно, а из оставшихся видов спорта выбирается $n - 1$ (соревнование по $(n + 1)$-му виду спорта может проводиться любым номером). Тогда может оказаться, что все, кроме одного спортсмена (а именно, кроме самого слабого в $(n + 1)$-м виде спорта), являются возможными победителями, а единственный исключительный участник (будем называть его аутсайдером) может выйти в финал.
База $(n = 1)$ очевидна.
Индуктивный переход. Строим пример $E_{n+1}$, исходя из существования примера $E_n$. Опять разделим $2^{n+1}$ спортсменов на равные группы $B$ и $B^{ \prime}$. Определим их силы так, чтобы в 1-м виде спорта любой из $B^{ \prime}$ был сильнее любого из $B$, в остальных видах - наоборот, а в виде $j$ ($2 \leq j \leq n + 2$) спортсмены внутри каждой из групп $B$ и $B^{ \prime}$ были упорядочены, как спортсмены в примере $E_n$ в виде $j - 1$. Дополнительно потребуем, чтобы аутсайдер в $B$ был самым сильным среди $B$ в 1-м виде спорта.
Проводя сначала соревнования по 1-му виду спорта, получим $2^n - 1$ возможных победителей из $B^{ \prime}$, причем при некотором порядке проведения соревнований аутсайдер из $B^{ \prime}$ выйдет в финал (индуктивное предположение).
Если вообще не проводить соревнования по 1-му виду спорта, то в первом соревновании выбывают все спортсмены из $B^{ \prime}$, а далее проводится $n$ соревнований. По предположению индукции, выбрав вид спорта для первого соревнования и порядок проведения соревнований по остальным видам спорта, можно сделать победителями $2^n - 1$ спортсменов из $B$.
Осталось объяснить, как сделать победителем аутсайдера в $B$. Для этого первым проводим тот вид соревнований, который является последним при порядке соревнований, обеспечивающем выход аутсайдера в финал. После этого останутся только спортсмены из $B$. Далее проводим соревнования в таком порядке, который обеспечивает выход аутсайдера из $B$ в финал, а завершаем - 1-м видом спорта. В нем аутсайдер побеждает.
