Войскунский В.

Сегодня — фигурное катаниеВойскунский В. Сегодня — фигурное катание // Квант. — 1977. — № 12. — С. 30‍—‍32.‍‍

Спорт многолик. Он — источник здоровья, переживаний болельщиков и математических задач. Есть виды спорта, хорошо «освоенные» математиками, например — шахматы. Сегодня мы займёмся фигурным катанием.

Мы рассмотрим ряд задач, связанных с правилами определения мест, занятых фигуристами в соревнованиях.

Судейство соревнований по фигурному катанию осуществляют несколько арбитров. Наиболее ответственные соревнования судят девять арбитров, поэтому при дальнейшем изложении мы будем считать, что арбитров, осуществляющих судейство, — девять.

Окончилось соревнование. Каждый из девяти арбитров «расставил» участников по местам. Предполагается, что каждый арбитр даёт всем спортсменам разные места (нельзя, чтобы несколько спортсменов «поделили» какое-то место). Итак, в результате соревнований каждый из арбитров «присваивает» каждому фигуристу определённое место; набор мест, полученный фигуристом, будем называть комплектом оценок.

Как в итоге устанавливается место, занятое каждым фигуристом в соревновании? У зрителей, наблюдающих соревнования по фигурному катанию, иногда создаётся впечатление, что это определяется суммой мест: складываются места, присвоенные участнику каждым арбитром. Однако это не так.

Правило определения мест таково: первое место занимает спортсмен, комплект оценок которого имеет наибольшее количество первых мест; если несколько фигуристов имеют одинаковое количество первых мест, то предпочтение отдаётся тем, у кого больше вторых мест; в случае равенства вторых мест — тем, у кого больше третьих мест, и т. д.; после того, как первое место «присвоено», в комплектах оценок остальных спортсменов «1» заменяется на «2»; затем второе место занимает спортсмен, комплект оценок которого имеет наибольшее количество вторых мест; при равенстве количества вторых мест сравнивают количества третьих мест и т. д.; после того, как первые $m-1$‍‍ мест «присвоены», в комплектах оценок остальных спортсменов «$m-1$‍‍» заменяется на «$m$‍‍»‍, затем определяется $m$‍‍-е место; если у двух фигуристов, претендующих на одно место, количества каждых мест одинаковы, предпочтение отдаётся участнику, у которого сумма мест в первоначальном комплекте оценок меньше.

Реальная ситуация гораздо сложнее, в частности потому, что соревнования по фигурному катанию — многоборье. После окончания соревнований в отдельном виде многоборья каждый арбитр выставляет каждому спортсмену определённый балл (эти баллы при показе соревнований по телевидению показываются на экране). В зависимости от баллов, «присвоенных» участникам данным арбитром, они «расставляются» по местам: чем выше балл, тем выше место, т. е. меньше его номер. После окончания всех видов многоборья для каждого фигуриста подсчитывается «итоговый» балл, полученный им от каждого арбитра, причём осуществляется не простое сложение баллов, полученных в каждом виде многоборья, а более сложный подсчёт. В соответствии с «итоговыми» баллами фигуристы вновь получают у каждого из арбитров определённое место. Из этих-то мест и составляется комплект оценок, о котором говорилось выше.

По сформулированному правилу фигурист с лучшей (меньшей) суммой мест из комплекта оценок иногда получает худшее (большее) место. Такие случаи встречались в практике фигурного катания, причём в соревнованиях самого высокого ранга. Так, на чемпионате мира по фигурному катанию 1975 года, который проходил в Колорадо-Спрингс, В. Ковалёв с суммой мест 27 занял второе место, а Д. Карри с суммой мест 23 — третье. Приведём фрагмент таблицы распределения мест, полученных спортсменами от арбитров в этих соревнованиях, для фигуристов, занявших в результате первые шесть мест: $$ \def\c#1{\colsep{0pt}{\begin{array}{c}#1\end{array}}} \def\f#1{\enspace\mathrlap{#1}\hphantom{\text{Овчинников}}\enspace} \def\r{\rule[-3.5pt]{.4pt}{12pt}} \def\strut{\rule[-4.5pt]{0pt}{14pt}} \def\A#1#2#3#4#5#6#7#8#9{ \hskip.75em\mathclap{#1}\hskip.75em\r \hskip.75em\mathclap{#2}\hskip.75em\r \hskip.75em\mathclap{#3}\hskip.75em\r \hskip.75em\mathclap{#4}\hskip.75em\r \hskip.75em\mathclap{#5}\hskip.75em\r \hskip.75em\mathclap{#6}\hskip.75em\r \hskip.75em\mathclap{#7}\hskip.75em\r \hskip.75em\mathclap{#8}\hskip.75em\r \hskip.75em\mathclap{#9}\hskip.75em} \colsep{0pt}{\begin{array}{|c|c|c|c|}\hline \text{Фигуристы}&\c{\text{Номера арбитров}\strut\\\hline\A123456789}&\enspace\c{\text{Занятое}\\[-2pt]\text{место}}\enspace&\enspace\c{\text{Сумма}\\[-2pt]\text{мест}}\enspace\\ \hline &\A{}{}{}{}{}{}{}{}{}&&\\[-6pt] \f{Волков} &\A111111313&1&13\\ \f{Ковалёв} &\A224252424&2&27\\ \f{Карри} &\A333323231&3&23\\ \f{Крэнстон} &\A542434142&4&29\\ \f{Маккеллен} &\A655545567&5&48\\ \f{Овчинников}&\A467676755&6&53\\[-6pt] &\A{}{}{}{}{}{}{}{}{}&&\\ \hline \end{array}} $$

Итак, не всегда фигурист, получивший минимальную сумму мест, займёт первое место. А существует ли сумма мест, гарантирующая фигуристу первое место? Безусловно. Например, девять. Естественно возникает вопрос: какова максимальная величина $\alpha_1$‍‍ такая, что любая сумма мест, меньшая или равная $\alpha_1$‍,‍ гарантирует фигуристу первое место? Подобный вопрос может быть поставлен относительно любого места, которое фигурист может занять в соревнованиях. Это и есть основная наша

Задача. В соревнованиях по фигурному катанию приняли участие $n$‍‍ спортсменов. Для каждого $k$‍‍ ($1\le k\le n$‍)‍ определить наибольшее число $\alpha_k$‍‍ такое, что любая сумма мест, меньшая или равная $\alpha_k$‍‍ гарантирует фигуристу, получившему её, место не ниже $k$‍‍-го. Предположим для простоты, что никакие два фигуриста не получили одинаковых сумм мест.

Случай $k=n$‍‍ тривиален, так как в этом случае при любой сумме мест, полученной фигуристом, он займёт место не ниже $k$‍‍-го. Поэтому $\alpha_n=9n$‍.‍

Рассмотрим случай $k=1$‍.‍ Покажем, что $\alpha_1=13$‍.‍ Рассмотрим следующее возможное распределение мест, полученных спортсменами от арбитров: $$ \def\c#1{\colsep{0pt}{\begin{array}{c}#1\end{array}}} \def\f#1{\enspace\mathrlap{#1}\hphantom{\text{Овчинников}}\enspace} \def\r{\rule[-3.5pt]{.4pt}{12pt}} \def\strut{\rule[-4.5pt]{0pt}{14pt}} \let\.\cdot \def\A#1#2#3#4#5#6#7#8#9{ \hskip.75em\mathclap{#1}\hskip.75em\r \hskip.75em\mathclap{#2}\hskip.75em\r \hskip.75em\mathclap{#3}\hskip.75em\r \hskip.75em\mathclap{#4}\hskip.75em\r \hskip.75em\mathclap{#5}\hskip.75em\r \hskip.75em\mathclap{#6}\hskip.75em\r \hskip.75em\mathclap{#7}\hskip.75em\r \hskip.75em\mathclap{#8}\hskip.75em\r \hskip.75em\mathclap{#9}\hskip.75em} \colsep{0pt}{\begin{array}{|c|c|c|}\hline \c{\text{Номера арбитров}\strut\\\hline\A123456789}&\enspace\c{\text{Занятое}\\[-2pt]\text{место}}\enspace&\enspace\c{\text{Сумма}\\[-2pt]\text{мест}}\enspace\\ \hline \A{}{}{}{}{}{}{}{}{}&&\\[-6pt] \A111112222&1&13\\ \A222221111&2&14\\ \A333333333&3&27\\ \A444444444&4&36\\[-3pt] \A\.\.\.\.\.\.\.\.\.&\.&\.\\[-7pt] \A\.\.\.\.\.\.\.\.\.&\.&\.\\[-7pt] \A\.\.\.\.\.\.\.\.\.&\.&\.\\[-3pt] \A nnnnnnnnn&n&9n\\[-6pt] \A{}{}{}{}{}{}{}{}{}&&\\ \hline \end{array}} $$ Из этой таблицы вытекает, что $\alpha_1\le13$‍,‍ так как в ней спортсмен с суммой мест 14 имеет второе место. Нам осталось показать, что если фигурист получит сумму мест $s$‍‍ не больше 13, то он займёт первое место. Допустим, что в этом случае фигурист получил $n_1$‍‍ первых мест и $l$‍‍ мест ниже первого, $n_1+l=9$‍.‍ С одной стороны, $s\ge n_1+2l=18-n_1$‍.‍ С другой стороны, $s\le13$‍.‍ Отсюда $n_1\ge5$‍,‍ значит, в рассматриваемом случае фигурист займёт первое место.

Упражнение 1. Доказать, что $\alpha_2=\begin{cases}17&n=3\\16&n=4.\end{cases}$‍‍

Упражнение 2. Доказать, что $\alpha_3=18$‍.‍

Оказывается, для остальных $k$‍‍ (т. е. $4\le k\lt n$‍)‍ $\alpha_k=k+16$‍.‍

Упражнение 3. Для любого $k$‍:‍ $4\le k\lt n$‍‍ построить таблицу распределения мест, полученных спортсменами от арбитров, в которой некоторый участник имеет сумму мест $k+17$‍‍ и занимает ($k+1$‍)‍-е место.

Из упражнения 3 вытекает, что при рассматриваемых $k$‍‍ $$ \alpha_k\le k+16.\tag1 $$

Упражнение 4. Сколько существует разных таблиц с указанным в упражнении 3 свойством? Две таблицы считаются разными, если в одной из них есть комплект оценок, которого нет в другой таблице, причём два комплекта оценок различны, если для некоторого $i$‍:‍ $1\le i\le n$‍‍ число $i$‍‍-х мест в одном комплекте не равно числу i-х мест в другом комплекте.

Упражнение 5. Доказать, что если сумма мест фигуриста не превосходит 20, то он занимает место не ниже четвёртого.

Упражнение 6. Для любого $k$‍:‍ $4\le k\lt n$‍‍ доказать, что если сумма мест фигуриста не превосходит $k+16$‍‍ и в его комплекте оценок есть места больше $k$‍‍-го, то он занимает место не ниже $k$‍‍-го.

Докажем методом математической индукции, что при $k$‍:‍ $4\le k\lt n$‍‍ сумма мест, не превосходящая $k+16$‍,‍ гарантирует фигуристу место не ниже $k$‍‍-го. Отсюда и из (1) следует $\alpha_k=k+16$‍.‍

Базис индукции. $k=4$‍‍ — вытекает из упражнения 5.

Индукционный шаг. Предположим, что при $l$‍:‍ $4\le l\lt n-1$‍‍ сумма мест, не превосходящая $l+16$‍,‍ гарантирует фигуристу место не ниже $l$‍‍-го. Докажем, что тогда сумма мест, не превосходящая $l+17$‍,‍ гарантирует место не ниже ($l+1$‍)‍-го. Допустим противное: фигурист $A$‍‍ имеет сумму мест, не превосходящую $l+17$‍,‍ и место ниже ($l+1$‍)‍-го. Из упражнения 6 вытекает, что в комплекте оценок фигуриста $A$‍‍ все места не превосходят $l+1$‍.‍ Но тогда и в комплекте оценок фигуриста $B$‍,‍ имеющего ($l+1$‍)‍-е место, все места не превосходят $l+1$‍.‍ Из наших правил и условия задачи вытекает, что сумма мест фигуриста $B$‍‍ меньше суммы мест фигуриста $A$‍.‍ Значит, она не превосходит $l+16$‍.‍ А это уже противоречит предположению индукции.

Наше утверждение доказано. Тем самым мы полностью решили нашу задачу.

Опустим в нашей задаче условие о том, что никакие два фигуриста не получили одинаковых сумм мест. Тогда несколько фигуристов могут иметь одинаковые комплекты оценоќ. В этом случае давайте считать, что все эти фигуристы заняли одинаковое место. Например, если каждый из двух фигуристов с одинаковыми комплектами оценок может занять четвёртое место, то будем считать, что они оба заняли четвёртое место, а остальные фигуристы претендуют не на пятое, а на шестое место.

Упражнение 7. Доказать, что, как бы мы ни дополнили Правило определения мест, при любом $4\le k\lt n$‍‍ фигурист, получивший сумму мест $k+16$‍,‍ может занять место ниже $k$‍‍-го.

Предположим, что сумма мест у фигуриста, занявшего первое место, не совпадает ни с одной из сумм мест, полученных остальными фигуристами.

Попробуйте установить, можно ли так при этом дополнить Правило определения мест, чтобы все результаты нашей задачи остались без изменений.

Попробуйте также решить нашу задачу, если число арбитров на соревнованиях равно 2, 7, $p$‍.‍