Разделы 
Дополнительно
Задача по математике - 3739
2019-06-16 
В чемпионате мира и Европы участвуют 20 команд. Среди них имеется $k$ европейских команд, результаты встреч между которыми на чемпионате мира идут в зачет чемпионата Европы. Чемпионат проводится в один круг.
При каком наибольшем $k$ может оказаться, что команда, набравшая строго наибольшее количество очков в чемпионате Европы, наберет строго наименьшее количество очков в чемпионате мира, если это:
а) чемпионат по хоккею (допускаются ничьи)?
б) чемпионат по волейболу (ничьих не бывает)?
Решение:
Мы рассмотрим сразу случай $n$ команд - участников чемпионата мира.
a) Общее количество очков, разыгрываемых в чемпионате мира (за победу - 2 очка, за ничью - 1, за поражение - 0), равно $n(n - 1)$, в чемпионате Европы - $k(k-1)$.
Пусть $x$ - количество очков, набранных чемпионом Европы в играх чемпионата мира, а $у$ - количество очков, полученных им в играх с европейскими командами $x \geq у$. Пусть каждая из остальных команд набрала в играх чемпионата мира больше чем $x$ очков, т, е. не меньше чем $x + 1$ очко. Тогда $x + (n - 1) (x + 1) \leq n(n-1)$, или $x \leq n - 2 + \frac{1}{n}$, а так как $x$ - целое число, то $x \leq n - 2$.
Каждая из остальных европейских команд набрала не больше $у - 1$ очков в чемпионате Европы и потому $y + (y - 1) (k - 1) \geq k(k-1)$, или $у \geq k - \frac{1}{k}$, а поскольку $у$ - целое число, $y \geq k$. Итак, $k \leq y \leq x \leq n - 2$, т. е. $k \leq n - 2$.
На рис. а приведен пример турнирной таблицы, показывающий, что чемпион Европы (третья команда) может занять последнее место в чемпионате мира.
а) Ответ: $k = n - 2$, если $n \geq 3$ (в частности, при $n = 20$ получим $k = 18$).
б) В чемпионате по волейболу победившая команда получает 1 очко, потерпевшая поражение - 0 очков, так что разыгрывается ровно $\frac{n(n-1)}{2}$ очков. Рассмотрим подробно случай четного $n = 2l$.
Рассуждая, как и выше, получим ($x, у$ - те же, что и в случае а))
$x + (2l - 1) (x + 1 ) \leq \frac{2l(2l - 1)}{2} = l(2l - 1)$, (1)
$y + (k- 1)(y-1) \geq \frac{k(k-1)}{2}$. (2)
Из равенства (1) следует, что $x \leq l - \frac{3}{2} + \frac{1}{2l}$. Поэтому $x \leq l - 2$. Из неравенств $l - 2 \geq x \geq y$ и неравенства (2) следует, что
$k^2 + (5 - 2l) k - 2 \leq 0$. (3)
При $l \geq 4$ наибольшее целое $k$, удовлетворяющее неравенству (3), равно $2l - 5$ (при $k = 2l - 5$ неравенство (3) справедливо, а при $k = 2l - 4$ его левая часть положительна).
Теперь докажем, что равенство $k = 2l - 5 = n - 5$ при $l \geq 4$ возможно. На рис. 90, в приведена турнирная таблица для $n = 8, k = 3$ (последние 3 команды - европейские)» Эта таблица послужит началом индукции.
Дальнейшие построения проводим по индукции, добавляя на каждом шагу по 2 европейские команды.
Заметим прежде всего, что при $k = 2l - 5$ непременно $x = у = l - у$. В самом деле,
$y \geq \frac {(k-1)(k+2)}{2k} = \frac{k}{2} + \frac{1}{2} - \frac{1}{2k}$, или $y \geq l - 2 - \frac{1}{2(2l-5)}$,
а так как $у$ - целое число, то $у = l - 2 = x$. Это значит, что чемпион Европы проиграл всем неевропейским командам.
Теперь предположим, что уже реализована таблица чемпионата с $k = n - 5 = 2l - 5$. Добавим две европейские команды $A$ и $В$ по следующему правилу: команда $A$ выигрывает у старых команд с нечетными номерами и у команды $В$ и проигрывает остальным; команда $В$ выигрывает у команд с четными номерами и проигрывает остальным. Каждая из прежних команд получает в результате по одному очку, так что их взаимное положение не меняется.
У чемпиона Европы теперь $l - 1$ очко, у команды $A - l + 1$ очко; у команды $В$ - $l$ очков, так что старый чемпион Европы по-прежнему на последнем месте. В играх же с европейскими командами команда $A$ наберет $l - 2$ очка ($l - 3$ в играх со «старыми» командами и одно - с командой $В$); команда $В$ в играх с европейскими командами также наберет $l - 2$ очка, так что чемпион Европы останется прежним.
Случаи нечетных $n = 2l - 1$ при $l \geq 4$, а также $n \leq 6$ рассматриваются аналогично (рис. в, г, д).
Ответ: $k = n - 5$ при четном $n \geq 8$ (в частности,$k = 15$ при $n = 20$), $k = n - 4$ при нечетном $n \geq 7$; $k = 2$ при $n = 6$ и $n = 5$.
В чемпионате мира и Европы участвуют 20 команд. Среди них имеется $k$ европейских команд, результаты встреч между которыми на чемпионате мира идут в зачет чемпионата Европы. Чемпионат проводится в один круг.
При каком наибольшем $k$ может оказаться, что команда, набравшая строго наибольшее количество очков в чемпионате Европы, наберет строго наименьшее количество очков в чемпионате мира, если это:
а) чемпионат по хоккею (допускаются ничьи)?
б) чемпионат по волейболу (ничьих не бывает)?
Решение:
Мы рассмотрим сразу случай $n$ команд - участников чемпионата мира.
a) Общее количество очков, разыгрываемых в чемпионате мира (за победу - 2 очка, за ничью - 1, за поражение - 0), равно $n(n - 1)$, в чемпионате Европы - $k(k-1)$.
Пусть $x$ - количество очков, набранных чемпионом Европы в играх чемпионата мира, а $у$ - количество очков, полученных им в играх с европейскими командами $x \geq у$. Пусть каждая из остальных команд набрала в играх чемпионата мира больше чем $x$ очков, т, е. не меньше чем $x + 1$ очко. Тогда $x + (n - 1) (x + 1) \leq n(n-1)$, или $x \leq n - 2 + \frac{1}{n}$, а так как $x$ - целое число, то $x \leq n - 2$.
Каждая из остальных европейских команд набрала не больше $у - 1$ очков в чемпионате Европы и потому $y + (y - 1) (k - 1) \geq k(k-1)$, или $у \geq k - \frac{1}{k}$, а поскольку $у$ - целое число, $y \geq k$. Итак, $k \leq y \leq x \leq n - 2$, т. е. $k \leq n - 2$.
На рис. а приведен пример турнирной таблицы, показывающий, что чемпион Европы (третья команда) может занять последнее место в чемпионате мира.
а) Ответ: $k = n - 2$, если $n \geq 3$ (в частности, при $n = 20$ получим $k = 18$).
б) В чемпионате по волейболу победившая команда получает 1 очко, потерпевшая поражение - 0 очков, так что разыгрывается ровно $\frac{n(n-1)}{2}$ очков. Рассмотрим подробно случай четного $n = 2l$.
Рассуждая, как и выше, получим ($x, у$ - те же, что и в случае а))
$x + (2l - 1) (x + 1 ) \leq \frac{2l(2l - 1)}{2} = l(2l - 1)$, (1)
$y + (k- 1)(y-1) \geq \frac{k(k-1)}{2}$. (2)
Из равенства (1) следует, что $x \leq l - \frac{3}{2} + \frac{1}{2l}$. Поэтому $x \leq l - 2$. Из неравенств $l - 2 \geq x \geq y$ и неравенства (2) следует, что
$k^2 + (5 - 2l) k - 2 \leq 0$. (3)
При $l \geq 4$ наибольшее целое $k$, удовлетворяющее неравенству (3), равно $2l - 5$ (при $k = 2l - 5$ неравенство (3) справедливо, а при $k = 2l - 4$ его левая часть положительна).
Теперь докажем, что равенство $k = 2l - 5 = n - 5$ при $l \geq 4$ возможно. На рис. 90, в приведена турнирная таблица для $n = 8, k = 3$ (последние 3 команды - европейские)» Эта таблица послужит началом индукции.
Дальнейшие построения проводим по индукции, добавляя на каждом шагу по 2 европейские команды.
Заметим прежде всего, что при $k = 2l - 5$ непременно $x = у = l - у$. В самом деле,
$y \geq \frac {(k-1)(k+2)}{2k} = \frac{k}{2} + \frac{1}{2} - \frac{1}{2k}$, или $y \geq l - 2 - \frac{1}{2(2l-5)}$,
а так как $у$ - целое число, то $у = l - 2 = x$. Это значит, что чемпион Европы проиграл всем неевропейским командам.
Теперь предположим, что уже реализована таблица чемпионата с $k = n - 5 = 2l - 5$. Добавим две европейские команды $A$ и $В$ по следующему правилу: команда $A$ выигрывает у старых команд с нечетными номерами и у команды $В$ и проигрывает остальным; команда $В$ выигрывает у команд с четными номерами и проигрывает остальным. Каждая из прежних команд получает в результате по одному очку, так что их взаимное положение не меняется.
У чемпиона Европы теперь $l - 1$ очко, у команды $A - l + 1$ очко; у команды $В$ - $l$ очков, так что старый чемпион Европы по-прежнему на последнем месте. В играх же с европейскими командами команда $A$ наберет $l - 2$ очка ($l - 3$ в играх со «старыми» командами и одно - с командой $В$); команда $В$ в играх с европейскими командами также наберет $l - 2$ очка, так что чемпион Европы останется прежним.
Случаи нечетных $n = 2l - 1$ при $l \geq 4$, а также $n \leq 6$ рассматриваются аналогично (рис. в, г, д).
Ответ: $k = n - 5$ при четном $n \geq 8$ (в частности,$k = 15$ при $n = 20$), $k = n - 4$ при нечетном $n \geq 7$; $k = 2$ при $n = 6$ и $n = 5$.
