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

Проект МЦНМО
при участии
школы 57
Задача 64436
Темы:    [ Упорядочивание по возрастанию (убыванию) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы: 6,7,8,9,10,11
В корзину
Прислать комментарий

Условие

Имеется 36 борцов. У каждого некоторый уровень силы, и более сильный всегда побеждает более слабого, а равные по силе сводят поединок вничью. Всегда ли этих борцов можно разбить на пары так, что все победители в парах будут не слабее, чем все те, кто сделал ничью или проиграл, а все сделавшие ничью будут не слабее всех тех, кто проиграл?


Решение

  Упорядочим борцов по силе (борцы равной силы идут подряд), и пусть борцы из более сильной половины встречаются с борцами из более слабой.
  Все победители – из более сильной половины, проигравшие – из более слабой. Пусть борец А из первой половины сделал ничью с борцом Б из второй (и значит, равен ему по силе). Так как А не слабее любого борца из второй половины, то А и Б не слабее всех проигравших и сделавших ничью. Так как Б не сильнее любого борца из первой половины, то А и Б не сильнее всех победителей и сделавших ничью. Как следствие, А и Б равны по силе всем сделавшим ничью.


Ответ

Всегда.

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

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2013
задача
Номер 3

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

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