Разделы 
Дополнительно
Задача по математике - 3333
2019-06-02 
В круговом шахматном турнире каждый участник сыграл с каждым один раз. Назовем партию неправильной, если выигравший ее шахматист в итоге набрал очков меньше, чем проигравший. (Победа дает 1 очко, ничья - 1/2, поражение - 0.)
Могут ли неправильные партии составлять
а) более 75 % от общего количества партий в турнире;
б) более 70 %?
Решение:
а) Пусть $N$ - число игроков, $M = \left [ \frac{N}{2} \right ]$. Игроков, занявших первые $M$ мест, назовем сильными, а остальных - слабыми (между участниками с одинаковой суммой очков места распределяются произвольно). Пусть $X$ - число правильных партий между сильными и слабыми. Сумма очков, набранных сильными во встречах между собой, равна $\frac{M(M-1)}{2}$, а во встречах со слабыми - не больше $X$. Обозначим сумму очков, набранных сильными, через $S_1$, а сумму очков, набранных слабыми, - через $S_2$. Тогда
$S_1 \leq \frac{M(M-1)}{2} + X$, $S_1 + S_2 = \frac{N(N-1)}{2}$.
Если все получили одинаковое число очков, то все партии - правильные. Поэтому можно считать, что есть два игрока с разным числом очков. Рассмотрим сначала, случай, когда $N$ - четное. Тогда число слабых игроков равно числу сильных. Ясно, что в этом случае $S_1 > S_2$. Значит,
$S_1 > \frac{S_1 + S_2}{2} = \frac{N(N-1)}{4}$,
откуда
$X \geq S_1 - \frac{M(M - 1)}{2} > \frac{N(N - 1)}{4} - \frac{M(M - 1)}{2}$.
Подставляя $M = N/2$, несложной выкладкой убеждаемся, что $X > \frac{N^2}{8} > \frac{N(N - 1)}{8}$. Так как общее число партий равно $\frac{N(N - 1)}{2}$, доля правильных партий больше 1/4.
Однако это доказательство не проходит для нечетного $N$. В этом случае можно поступить так: рассмотрим средний результат сильного игрока $\frac{S_{1}}{M}$. Ясно, что он больше среднего результата слабого игрока, а значит, больше среднего, взятого по всем игрокам:
$\frac{S_1}{M} > \frac{N(N - 1)/2}{N}$.
То есть $S_1 > \frac{M(N - 1)}{2}$. Отсюда
$X \geq S_1 - \frac{M(M-1)}{2} > \frac{M(N-M)}{2} > \frac{N(N-1)}{8}$.
Последнее неравенство нетрудно проверить, подставив $M = \frac{N-1}{2}$.
б) Рассмотрим сначала турнир из $2k + 1$ игрока, в котором каждый участник с номером $i \leq k$ проиграл участникам с номерами $i + 1, \cdots, i + k$ и выиграл у остальных, а каждый участник с номером $i > k$ выиграл у участников с номерами $i - k, \cdots , i - 1$ и проиграл остальным. Очевидно, что все игроки набрали по $k$ очков.
Рассмотрим таблицу турнира (рис.). Нетрудно видеть, что в этой таблице над главной диагональю единицы стоят ровно в $\frac{k(k+1)}{2}$ клетках из $\frac{2k(2k+1)}{2}$. Теперь «размножим» каждого игрока, заменив его группой из $n$ игроков, и пусть участники из разных групп играют друг с другом так же, как соответствующие прежние участники, а участники из одной группы играют друг с другом вничью. Получим новую таблицу, в которой по-прежнему у всех игроков поровну очков.
Исправим эту таблицу так, чтобы суммы очков игроков перестали быть равными. Для этого будем менять результаты участников из $(k + 1)$-й группы: в их встречах против участников из $(k + 1 - i)$ -й группы заменим $in$ выигрышей ничьими, так что сумма очков каждого участника $(k + 1)$-й группы уменьшится на $i/2$, а каждого участника $(k + 1 - i)$-й группы увеличится на $i/2$. Напротив, в партиях с игроками $(k + 1 + i)$-й группы заменим ничьими $in$ проигрышей.
Тогда первое место в турнире займут игроки из первой группы, второе - из второй группы и т. д. Посчитаем число неправильных партий.
Все партии, проигранные игроками из группы $i \leq k$, - неправильные. Таких партий $kn^2 - in$ (вспомним, что $in$ партий с игроками из $(k + 1)$-й группы сыграны вничью). Далее, игроки из $i$-й группы при $i > k +1$ проиграли $(2k + 1 - i)n^2$ неправильных партий. Наконец, игроки из $(k + 1)$-й группы проиграли $kn^2 - \frac{k(k + 1)n}{2}$ неправильных партий (второе слагаемое соответствует неправильным проигрышам, которые мы заменили на ничьи).
Итак, число неправильных партий равно
$\sum_{i=1}^{k} (kn^2 - in) + \sum_{i=k+2}^{2k+1} (2k + 1 - i)n^2 + kn^2 - \frac{k(k+1)}{2} n = \frac{3k^2 + k}{2} n^2 - k(k+1)n$.
При этом общее число партий равно $\frac {n(2k+1)(n(2k+1) - 1)}{2}$. Значит, когда $к$ и $n$ стремятся к бесконечности одновременно, число неправильных партий растет как $\frac{3}{2} k^2n^2$, а число всех партий - как $2k^2n^2$. Тогда их отношение стремится к $\frac{3}{4} > 0,7$. Поэтому, если взять достаточно большие $n$ и $k$, это отношение будет больше 70 %. Читатель, который не любит пределов, может просто проверить, что при $n = k = 20$ неправильные партии составляют $\frac{235600}{335790} > 0,7$ от общего числа партий.
Ответ: а) Не могут; б) могут.
В круговом шахматном турнире каждый участник сыграл с каждым один раз. Назовем партию неправильной, если выигравший ее шахматист в итоге набрал очков меньше, чем проигравший. (Победа дает 1 очко, ничья - 1/2, поражение - 0.)
Могут ли неправильные партии составлять
а) более 75 % от общего количества партий в турнире;
б) более 70 %?
Решение:
а) Пусть $N$ - число игроков, $M = \left [ \frac{N}{2} \right ]$. Игроков, занявших первые $M$ мест, назовем сильными, а остальных - слабыми (между участниками с одинаковой суммой очков места распределяются произвольно). Пусть $X$ - число правильных партий между сильными и слабыми. Сумма очков, набранных сильными во встречах между собой, равна $\frac{M(M-1)}{2}$, а во встречах со слабыми - не больше $X$. Обозначим сумму очков, набранных сильными, через $S_1$, а сумму очков, набранных слабыми, - через $S_2$. Тогда
$S_1 \leq \frac{M(M-1)}{2} + X$, $S_1 + S_2 = \frac{N(N-1)}{2}$.
Если все получили одинаковое число очков, то все партии - правильные. Поэтому можно считать, что есть два игрока с разным числом очков. Рассмотрим сначала, случай, когда $N$ - четное. Тогда число слабых игроков равно числу сильных. Ясно, что в этом случае $S_1 > S_2$. Значит,
$S_1 > \frac{S_1 + S_2}{2} = \frac{N(N-1)}{4}$,
откуда
$X \geq S_1 - \frac{M(M - 1)}{2} > \frac{N(N - 1)}{4} - \frac{M(M - 1)}{2}$.
Подставляя $M = N/2$, несложной выкладкой убеждаемся, что $X > \frac{N^2}{8} > \frac{N(N - 1)}{8}$. Так как общее число партий равно $\frac{N(N - 1)}{2}$, доля правильных партий больше 1/4.
Однако это доказательство не проходит для нечетного $N$. В этом случае можно поступить так: рассмотрим средний результат сильного игрока $\frac{S_{1}}{M}$. Ясно, что он больше среднего результата слабого игрока, а значит, больше среднего, взятого по всем игрокам:
$\frac{S_1}{M} > \frac{N(N - 1)/2}{N}$.
То есть $S_1 > \frac{M(N - 1)}{2}$. Отсюда
$X \geq S_1 - \frac{M(M-1)}{2} > \frac{M(N-M)}{2} > \frac{N(N-1)}{8}$.
Последнее неравенство нетрудно проверить, подставив $M = \frac{N-1}{2}$.
б) Рассмотрим сначала турнир из $2k + 1$ игрока, в котором каждый участник с номером $i \leq k$ проиграл участникам с номерами $i + 1, \cdots, i + k$ и выиграл у остальных, а каждый участник с номером $i > k$ выиграл у участников с номерами $i - k, \cdots , i - 1$ и проиграл остальным. Очевидно, что все игроки набрали по $k$ очков.
Рассмотрим таблицу турнира (рис.). Нетрудно видеть, что в этой таблице над главной диагональю единицы стоят ровно в $\frac{k(k+1)}{2}$ клетках из $\frac{2k(2k+1)}{2}$. Теперь «размножим» каждого игрока, заменив его группой из $n$ игроков, и пусть участники из разных групп играют друг с другом так же, как соответствующие прежние участники, а участники из одной группы играют друг с другом вничью. Получим новую таблицу, в которой по-прежнему у всех игроков поровну очков.
Исправим эту таблицу так, чтобы суммы очков игроков перестали быть равными. Для этого будем менять результаты участников из $(k + 1)$-й группы: в их встречах против участников из $(k + 1 - i)$ -й группы заменим $in$ выигрышей ничьими, так что сумма очков каждого участника $(k + 1)$-й группы уменьшится на $i/2$, а каждого участника $(k + 1 - i)$-й группы увеличится на $i/2$. Напротив, в партиях с игроками $(k + 1 + i)$-й группы заменим ничьими $in$ проигрышей.
Тогда первое место в турнире займут игроки из первой группы, второе - из второй группы и т. д. Посчитаем число неправильных партий.
Все партии, проигранные игроками из группы $i \leq k$, - неправильные. Таких партий $kn^2 - in$ (вспомним, что $in$ партий с игроками из $(k + 1)$-й группы сыграны вничью). Далее, игроки из $i$-й группы при $i > k +1$ проиграли $(2k + 1 - i)n^2$ неправильных партий. Наконец, игроки из $(k + 1)$-й группы проиграли $kn^2 - \frac{k(k + 1)n}{2}$ неправильных партий (второе слагаемое соответствует неправильным проигрышам, которые мы заменили на ничьи).
Итак, число неправильных партий равно
$\sum_{i=1}^{k} (kn^2 - in) + \sum_{i=k+2}^{2k+1} (2k + 1 - i)n^2 + kn^2 - \frac{k(k+1)}{2} n = \frac{3k^2 + k}{2} n^2 - k(k+1)n$.
При этом общее число партий равно $\frac {n(2k+1)(n(2k+1) - 1)}{2}$. Значит, когда $к$ и $n$ стремятся к бесконечности одновременно, число неправильных партий растет как $\frac{3}{2} k^2n^2$, а число всех партий - как $2k^2n^2$. Тогда их отношение стремится к $\frac{3}{4} > 0,7$. Поэтому, если взять достаточно большие $n$ и $k$, это отношение будет больше 70 %. Читатель, который не любит пределов, может просто проверить, что при $n = k = 20$ неправильные партии составляют $\frac{235600}{335790} > 0,7$ от общего числа партий.
Ответ: а) Не могут; б) могут.
