Олимпиадная задача: Определение мест 32 боксёров за 15 дней по олимпийской математике
Задача
В соревновании участвуют 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) дней.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь