Олимпиадная задача Герко А. А. о возможных победителях в n-борье, алгебра и индукция

  а) Индукция по n. База очевидна: один победитель единственного соревнования из двоих – это уже половина.

  Пусть есть пример n соревнований для 2ⁿ спортсменов с 2^n–1 возможными победителями. Разделим 2ⁿ⁺¹ спортсменов на две равные группы A и A'. Будем считать, что в некотором виде соревнований a каждый спортсмен из A' сильнее всех из A, а в остальных видах – наоборот. Если первым соревнованием провести a, то останется группа A', если любое другое – останется группа A. Применяя индуктивное предположение к группам A и A' по отдельности, получаем пример с  2^n–1 + 2^n–1 = 2ⁿ  возможными победителями. б) Укажем для каждого вида соревнований спортсмена, который при любом порядке проведения соревнований выбывает в этом виде или раньше. Построение индуктивное.

  Для 1-го вида соревнований – это самый слабый в этом виде.

  Пусть уже построено такое множество  A_k = {a₁, ..., a_k}  спортсменов, что a_i выбывает в i-м виде соревнований или раньше.

  Обозначим через a_k+1 спортсмена, который в (k+1)-м виде слабее всех, не входящих в A_k. Докажем, что a_k+1 выбывает в (k+1)-м виде соревнования или раньше при любом порядке соревнований. Пусть (k+1)-й вид соревнований проходит r-м по порядку, а из множества A_k за первые  r – 1  соревнований выбыло w человек.

  После (k+1)-го вида соревнований должно пройти по крайней мере  k – w  соревнований с номерами 1, ..., k. Поэтому  k – w ≤ n – r < 2^n–r.

  В r-м по порядку виде соревнований выбывает  2^n–r > k – w  человек. Поэтому a_k+1 (если он не выбыл раньше) не проходит в следующее соревнование.   в) Докажем по индукции, что для всех  n ≥ 1   существует такой пример  n + 1  соревнований с 2ⁿ участниками, что, выбирая n соревнований и порядок их проведения, можно сделать победителями  2ⁿ – 1  участников, а единственному исключительному участнику (будем называть его аутсайдером) можно обеспечить выход в финал.

  База при  n = 1  очевидна.

  Шаг индукции. Строим пример  n + 2  соревнований с 2ⁿ⁺¹ участниками. Опять разделим спортсменов на равные две группы B и B'. Будем считать, что в некотором виде соревнований b любой из B' сильнее любого из B, а в остальных видах – наоборот. Каждая из групп по отдельности в видах соревнований, отличных от b, даёт пример выполнения доказываемого утверждения. Дополнительно предположим, что аутсайдер в B – самый сильный среди B в виде b.

  Проводя первым b, получим  2ⁿ – 1  возможных победителей из B', причём при некотором порядке аутсайдер из B' выйдет в финал по индуктивному предположению.

  Если вообще не проводить b, то в первом соревновании выбывают все из B', а далее проводится  n – 1  соревнование. По индуктивному предположению, выбором первого соревнования и порядка проведения остальных можно сделать победителями  2ⁿ – 1  спортсменов из B.

  Осталось объяснить, как сделать победителем аутсайдера в B. Для этого первым проводим тот вид соревнований, который является финальным при порядке, обеспечивающем выход аутсайдера в финал. После этого останутся только спортсмены из B. Далее проводим соревнования в таком порядке, который обеспечивает выход аутсайдера из B в финал, а завершаем – соревнованием b. В нём аутсайдер побеждает по построению примера.   Теперь повторим рассуждение из а), используя при индуктивном переходе более точную оценку, доказанную выше. База индукции по-прежнему очевидна. В индуктивном переходе заметим, что из группы A' победителями можно сделать  2ⁿ – n  человек, а из A –  2ⁿ – 1  человека. Итого получаем

2ⁿ – n + 2ⁿ – 1 = 2ⁿ⁺¹ – (n + 1)  возможных победителей.

Ответ задачи отсутствует