ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105058
Темы:    [ Турниры и турнирные таблицы ]
[ Индукция (прочее) ]
[ Разбиения на пары и группы; биекции ]
Сложность: 5+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Герко А.А.

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


Решение

  а) Индукция по 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)  возможных победителей.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 62
Год 1999
вариант
Класс 9
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .