|
|
 |
Условие
В соревновании участвуют 32 боксёра. Каждый боксёр в течение одного дня
может проводить только один бой. Известно, что все боксёры имеют разную силу,
и что сильнейший всегда выигрывает. Докажите, что за 15 дней можно определить место каждого боксёра.
(Расписание каждого дня соревнований составляется вечером накануне и в день
соревнований не изменяется.)
Решение
Лемма. Пусть 2n+1 участников соревнований разбиты на две группы по 2n боксёров, причём в каждой из групп боксёры уже упорядочены по силе. Тогда упорядочить всех боксёров можно за n + 1 день.
Доказательство. Индукция по n. База. При n = 1 утверждение очевидно.
Шаг индукции. По предположению индукции, за n дней соревнований мы сможем упорядочить 2n боксёров, занимающих чётные места в каждой из групп, а также 2n боксёров, занимающих нечётные места. Для окончательного упорядочивания всех боксёров достаточно одного дня, так как для каждого боксёра существует не более одного соперника, о котором не известно, сильнее он его или слабее. Действительно, если боксёр занимает в одной из групп чётное место, то известно, между какими двумя боксёрами другой группы, занимающими последовательные чётные места, он располагается по силе. Между этими двумя боксёрами в группе находится лишь один боксёр с нечётным местом.
Теперь докажем по индукции, что упорядочить 2n боксёров можно за ½ n(n + 1) дней. База (n = 1) очевидна.
Шаг индукции. Разобьём 2n боксёров на две равные группы. Каждую из них по предположению индукции можно независимо упорядочить за ½ n(n – 1) дней. По лемме для полного упорядочивания всех боксёров достаточно ещё n дней. Всего потребовалось ½ n(n – 1) + n = ½ n(n + 1) дней.
Замечания
1. 8 баллов.
2. В неверной формулировке задача предлагалась в Задачнике "Кванта" (задача М1310). Исправление и более подробное обсуждение см. в решениях Задачника ("Квант", 1992, №12).
