Разделы 
Дополнительно
Задача по математике - 2737
2019-04-29 
а) На спортивных соревнованиях выступают 20 спортсменов; судят соревнования 9 судей. Каждый судья расставляет в своем списке соревнующихся в порядке от 1-го до 20-го в соответствии с тем, как он расценил их выступления, причем впоследствии оказалось, что оценки всех судей разнятся не слишком значительно: ни один спортсмен не получил у двух судей места, отличающиеся более чем на три. В основу окончательного распределения мест положено «среднее место» спортсмена по оценкам 9 судей, т. е. сумма всех приписанных ему мест, деленная на число судей (на 9). Каково наибольшее возможное значение «среднего места» лучшего из 20 спортсменов?
б) Теннисная федерация присвоила квалификационные номера всем теннисистам страны: 1-й номер - сильнейшему из них, 2-й - следующему по силе, и т.д.; при этом известно, что в состязании теннисистов, номера которых в квалификационном списке разнятся более чем на две единицы, всегда побеждает теннисист с меньшим номером. 1024 теннисиста страны устраивают соревнования по олимпийской системе, т. е. так, что после каждого этапа соревнований все проигравшие выбывают из игры, а оставшиеся разбиваются на пары соперников в следующем туре случайным образам. Спрашивается, какой наибольший номер может иметь победитель таких соревнований?
Решение:
а) Ясно, что наименьшее значение «среднего места» равно 1 - это значение достигается, если все судьи приписали 1-е место одному и тому же спортсмену. С другой стороны, 5 или более спортсменов получить (у разных судей) первое место не могут: в самом деле, эти $n \geq 5$ спортсменов получили бы тогда в совокупности у девяти судей 9 первых мест и $9n - 9 \geq 9 \cdot 5 - 9 = 36$ иных мест (ибо всего 9 судей приписывают им $9n$ мест); по условию задачи ни одно из этих мест не может быть ниже 4-го, что невозможно, так как мест с 3-го по 4-е судьи указывают лишь $3 \cdot 9 = 27$. Таким образом, остается лишь рассмотреть случаи, когда 1-е место (у разных судей) получили 2, 3 или 4 спортсмена.
1. Если 1-е место судьями приписано лишь двум спортсменам, то один из них назван 1-м не менее чем пятью судьями - и так как остальными судьями он поставлен не ниже чем на 4-е место, то «среднее место» этого спортсмена не ниже $\frac{1}{9} (5 \cdot 1 + 4 \cdot 4) = \frac{21}{9} \left ( = 2 \frac{1}{3} \right )$.
2. Если 1-е место приписано трем спортсменам, то в совокупности эти спортсмены получили 9 первых мест и еще $3 \cdot 9 - 9 = 18$ иных мест, ни одно из которых не может быть ниже четвертого; но так как 9 судей могут указать лишь 9 четвертых мест, то в «худшем» случае наши спортсмены получили 9 четвертых и 9 третьих мест. Таким образом, общая сумма приписанных этим трем спортсменам мест не больше $9 \cdot 11 + 9 \cdot 4 + 9 \cdot 3 = 72$, в силу чего хоть один из них имеет не большую $\frac{72}{3} = 24$ сумму мест и «среднее место, не худшее $\frac{24}{9} \left ( = 2 \frac{2}{3} \right )$.
3. Наконец, если 1-е место приписано четырем спортсменам, то эти 4 лица получили в совокупности 9 первых мест и еще $4 \cdot 9 - 9 = 27$ иных мест, не низших 4-го; из них 9 могут быть 4-ми сто», не худшее местами, 9 - 3-ми и последние 9 -2-ми. Таким образом, общая сумма мест четырех спортсменов здесь равна $9 \cdot 1 + 9 \cdot 2 + 9 \cdot 3 + 9 \cdot 4 = 90 ( < 4 \cdot 23)$; а значит, лучший из этих четырех спортсменов имеет сумму мест, не большую 22, и «среднее место», не худшее $\frac{22}{9} \left (= 2 \frac{4}{9} < 2 \frac{2}{3} \right )$.
Итак, «среднее место» лучшего спортсмена никак не может быть ниже $2 \frac{2}{3}$; при этом равняться $2 \frac{2}{3}$ оно может лишь в том случае, когда каждый из трех лучших спортсменов получил у трех судей 1-е место, у трех других - 3-е и у трех последних - 4-е (так что в этом случае победителями соревнований явятся сразу три спортсмена).
б) Ясно, что после каждого тура соревнований номер сильнейшего из оставшихся участников соревнований не уменьшается; при этом увеличиться он может не более чем на 2 (если сильнейшего теннисиста случайно победил теннисист, номер которого на две единицы выше, чем у него). Так как $1024 = 2^{10}$ и после каждого тура число участников соревнований уменьшается вдвое, то всего мы будем иметь 10 туров соревнования, после которых останется лишь $2^{0} = 1$ теннисист — победитель соревнования. Поскольку после каждого тура номер лучшего из оставшихся теннисистов может возрасти на 2, то отсюда, как будто, вытекает, что победителем соревнований может оказаться 21-й по списку теннисист.
На самом деле, одиако, и 21-й теннисист не имеет шансов оказаться победителем. В самом деле, для этого необходимо, чтобы па каждом этапе соревнований выбывали два сильнейших игрока; другими словами, надо, чтобы в первом туре выбыли 1-й и 2-й игроки, проигравшие, соответственно, 3-му и 4-му; во втором туре выбыли 3-й и 4-й игроки, проигравшие, соответственно, 5-му и 6-му, и т. д. Но в таком случае в полуфинальных соревнованиях должны были выбыть- 17-й и 18-и игроки, проигравшие 19-му и 20-му; поэтому 19-й и 20-н игроки выходят в финал — й победителем соревнований становится один из них, а не игрок с номером 21.
Покажем, наконец, что 20-й игрок победителем соревнований оказаться может. В самом деле, при наличии всего $2^{1} = 2$ игроков, разумеется, победителем может оказаться игрок с номером $2 = 2 \cdot 1$; если же теннисистов $2^2 = 4$, то победителем может стать теннисист с номером $2 \cdot 2 = 4$: в паре первых двух игроков может победить 2-й, в паре двух других — 4-й, а 4-й, в принципе, может и выиграть финал у 2-го. Аналогично, если игроков $2^3 = 8$, то победителем может оказаться 6-й теннисист: в самом деле, если четверо сильнейших игроков попадут в одну подгруппу, то в ней сильнейшим может оказаться 4-й; во второй подгруппе 6-й теннисист может и выиграть у 5-го; при этом в финале он встретится с 4-м, которого может и победить. Точно так же с помощью метода математической индукции легко доказать, что победителем в соревнованиях $2^{n}$ теннисистов может оказаться (2n)-й по силе теннисист: для этого лишь надо, чтобы первые $2n - 2$ игрока попали в одну подгруппу из $2^{n - 1}$ игроков, где (в силу предположения индукции) победителем может стать $(2n - 2)$-й теннисист; во второй же подгруппе победителем вполне может стать (2n)-й игрок, которому после этого надо лишь в финале выиграть у $(2n - 2)$-го игрока, - может быть, и трудная, но возможная задача.
Ответ: а) 2 2/3. б) 20.
а) На спортивных соревнованиях выступают 20 спортсменов; судят соревнования 9 судей. Каждый судья расставляет в своем списке соревнующихся в порядке от 1-го до 20-го в соответствии с тем, как он расценил их выступления, причем впоследствии оказалось, что оценки всех судей разнятся не слишком значительно: ни один спортсмен не получил у двух судей места, отличающиеся более чем на три. В основу окончательного распределения мест положено «среднее место» спортсмена по оценкам 9 судей, т. е. сумма всех приписанных ему мест, деленная на число судей (на 9). Каково наибольшее возможное значение «среднего места» лучшего из 20 спортсменов?
б) Теннисная федерация присвоила квалификационные номера всем теннисистам страны: 1-й номер - сильнейшему из них, 2-й - следующему по силе, и т.д.; при этом известно, что в состязании теннисистов, номера которых в квалификационном списке разнятся более чем на две единицы, всегда побеждает теннисист с меньшим номером. 1024 теннисиста страны устраивают соревнования по олимпийской системе, т. е. так, что после каждого этапа соревнований все проигравшие выбывают из игры, а оставшиеся разбиваются на пары соперников в следующем туре случайным образам. Спрашивается, какой наибольший номер может иметь победитель таких соревнований?
Решение:
а) Ясно, что наименьшее значение «среднего места» равно 1 - это значение достигается, если все судьи приписали 1-е место одному и тому же спортсмену. С другой стороны, 5 или более спортсменов получить (у разных судей) первое место не могут: в самом деле, эти $n \geq 5$ спортсменов получили бы тогда в совокупности у девяти судей 9 первых мест и $9n - 9 \geq 9 \cdot 5 - 9 = 36$ иных мест (ибо всего 9 судей приписывают им $9n$ мест); по условию задачи ни одно из этих мест не может быть ниже 4-го, что невозможно, так как мест с 3-го по 4-е судьи указывают лишь $3 \cdot 9 = 27$. Таким образом, остается лишь рассмотреть случаи, когда 1-е место (у разных судей) получили 2, 3 или 4 спортсмена.
1. Если 1-е место судьями приписано лишь двум спортсменам, то один из них назван 1-м не менее чем пятью судьями - и так как остальными судьями он поставлен не ниже чем на 4-е место, то «среднее место» этого спортсмена не ниже $\frac{1}{9} (5 \cdot 1 + 4 \cdot 4) = \frac{21}{9} \left ( = 2 \frac{1}{3} \right )$.
2. Если 1-е место приписано трем спортсменам, то в совокупности эти спортсмены получили 9 первых мест и еще $3 \cdot 9 - 9 = 18$ иных мест, ни одно из которых не может быть ниже четвертого; но так как 9 судей могут указать лишь 9 четвертых мест, то в «худшем» случае наши спортсмены получили 9 четвертых и 9 третьих мест. Таким образом, общая сумма приписанных этим трем спортсменам мест не больше $9 \cdot 11 + 9 \cdot 4 + 9 \cdot 3 = 72$, в силу чего хоть один из них имеет не большую $\frac{72}{3} = 24$ сумму мест и «среднее место, не худшее $\frac{24}{9} \left ( = 2 \frac{2}{3} \right )$.
3. Наконец, если 1-е место приписано четырем спортсменам, то эти 4 лица получили в совокупности 9 первых мест и еще $4 \cdot 9 - 9 = 27$ иных мест, не низших 4-го; из них 9 могут быть 4-ми сто», не худшее местами, 9 - 3-ми и последние 9 -2-ми. Таким образом, общая сумма мест четырех спортсменов здесь равна $9 \cdot 1 + 9 \cdot 2 + 9 \cdot 3 + 9 \cdot 4 = 90 ( < 4 \cdot 23)$; а значит, лучший из этих четырех спортсменов имеет сумму мест, не большую 22, и «среднее место», не худшее $\frac{22}{9} \left (= 2 \frac{4}{9} < 2 \frac{2}{3} \right )$.
Итак, «среднее место» лучшего спортсмена никак не может быть ниже $2 \frac{2}{3}$; при этом равняться $2 \frac{2}{3}$ оно может лишь в том случае, когда каждый из трех лучших спортсменов получил у трех судей 1-е место, у трех других - 3-е и у трех последних - 4-е (так что в этом случае победителями соревнований явятся сразу три спортсмена).
б) Ясно, что после каждого тура соревнований номер сильнейшего из оставшихся участников соревнований не уменьшается; при этом увеличиться он может не более чем на 2 (если сильнейшего теннисиста случайно победил теннисист, номер которого на две единицы выше, чем у него). Так как $1024 = 2^{10}$ и после каждого тура число участников соревнований уменьшается вдвое, то всего мы будем иметь 10 туров соревнования, после которых останется лишь $2^{0} = 1$ теннисист — победитель соревнования. Поскольку после каждого тура номер лучшего из оставшихся теннисистов может возрасти на 2, то отсюда, как будто, вытекает, что победителем соревнований может оказаться 21-й по списку теннисист.
На самом деле, одиако, и 21-й теннисист не имеет шансов оказаться победителем. В самом деле, для этого необходимо, чтобы па каждом этапе соревнований выбывали два сильнейших игрока; другими словами, надо, чтобы в первом туре выбыли 1-й и 2-й игроки, проигравшие, соответственно, 3-му и 4-му; во втором туре выбыли 3-й и 4-й игроки, проигравшие, соответственно, 5-му и 6-му, и т. д. Но в таком случае в полуфинальных соревнованиях должны были выбыть- 17-й и 18-и игроки, проигравшие 19-му и 20-му; поэтому 19-й и 20-н игроки выходят в финал — й победителем соревнований становится один из них, а не игрок с номером 21.
Покажем, наконец, что 20-й игрок победителем соревнований оказаться может. В самом деле, при наличии всего $2^{1} = 2$ игроков, разумеется, победителем может оказаться игрок с номером $2 = 2 \cdot 1$; если же теннисистов $2^2 = 4$, то победителем может стать теннисист с номером $2 \cdot 2 = 4$: в паре первых двух игроков может победить 2-й, в паре двух других — 4-й, а 4-й, в принципе, может и выиграть финал у 2-го. Аналогично, если игроков $2^3 = 8$, то победителем может оказаться 6-й теннисист: в самом деле, если четверо сильнейших игроков попадут в одну подгруппу, то в ней сильнейшим может оказаться 4-й; во второй подгруппе 6-й теннисист может и выиграть у 5-го; при этом в финале он встретится с 4-м, которого может и победить. Точно так же с помощью метода математической индукции легко доказать, что победителем в соревнованиях $2^{n}$ теннисистов может оказаться (2n)-й по силе теннисист: для этого лишь надо, чтобы первые $2n - 2$ игрока попали в одну подгруппу из $2^{n - 1}$ игроков, где (в силу предположения индукции) победителем может стать $(2n - 2)$-й теннисист; во второй же подгруппе победителем вполне может стать (2n)-й игрок, которому после этого надо лишь в финале выиграть у $(2n - 2)$-го игрока, - может быть, и трудная, но возможная задача.
Ответ: а) 2 2/3. б) 20.
