Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/06/55.pdf Дата изменения: Fri Dec 23 19:25:35 2005 Дата индексирования: Tue Oct 2 00:16:38 2012 Кодировка: Windows-1251 Поисковые слова: m 43

ОТВЕТЫ,

УКАЗАНИЯ,

РЕШЕНИЯ

55

сумма очков игрока А заведомо больше, чем число игроков, имеющих столько или больше, чем он. Как следствие, А не обладает свойством ( ). Ответ на поставленный вопрос теперь ясен: количество очков странного участника это наибольшее количество очков, которое меньше числа игроков, набравших столько или больше. Отметим, что мы заново решили задачу 1, поскольку не пользовались тем, что все странные имеют одинаковую сумму очков. Попутно возникает задача 3'. В каждом ли круговом турнире найдется участник со свойством ( )? А не имеющий этого свойства? Может ли в турнире быть участник с количеством очков, равным числу игроков, которые набрали столько или больше? Решение. Те, кто занял последнее место, заведомо обладают свойством ( ): наравне с ними или выше находятся все N участников турнира, тогда как сумма очков любого игрока не больше N 1. Напротив, игроки без свойства ( ) могут отсутствовать. Так будет, если число участников турнира N > 2, один из них проиграл всем остальным, а они сыграли между собой вничью. (См. также задачу 2 а).) Пусть теперь один из игроков выиграл у всех остальных, другой у всех, кроме первого, и т.д. Если число участников N четно, то имеется игрок с N/2 очками. Наравне с ним и выше находятся также N/2 участников. Таким образом, случай равенства рассматриваемых величин возможен. (Однако, ввиду показанного в решении задачи 3, он несовместим с наличием странных игроков.) 4. а) Согласно задаче 1 все странные игроки делят одно и то же место в турнирной таблице. Пусть это место не является первым. Тогда участник, находящийся на первом месте, проиграл всем странным. Но он выступил лучше, чем 'среднестатистический' игрок, и потому проиграл меньше матчей, чем выиграл. Значит, число проигранных им матчей меньше N/2 1 и (как целое) не больше [N/2] 1, что и требуется. Если же странные участники делят первое место, то аналогичное рассуждение можно применить к последнему месту. Можно и не опираться на задачу 1. Действительно, положим М = [N/2] 1. Пусть число странных больше М. Участник, занявший (или разделивший) первое место, проиграл не более М матчей. При этом он проиграл всем странным, не разделившим первое место. Значит, кто-то из странных получил первое место. Он, в свою очередь, проиграл не более М матчей, но при этом проиграл всем участникам, не разделившим первое место. Следовательно, большинство игроков делит первое место. Но аналогично и на последнем месте находится большинство, что противоречит предыдущему. б) Пусть М = [N/2], 1 L M - 1 , игроки занумерованы от 1 до N и разделены на четыре группы. В первую группу включим участников с номерами от 1 до L, во вторую от L + 1 до М, в третью от М + 1 до N L и в четвертую остальных. Пусть при этом игроки первой группы проиграли все матчи со второй группой и выиграли матчи с третьей и четвертой. Четвертая группа выиграла у второй и проиграла первой и третьей. Все остальные встречи закончились вничью. Нетрудно подсчитать, что игроки первой группы набрали по N M + (L 1)/2 очков, т.е. не меньше N/2. Игроки четвертой группы получили по M (L + 1)/2 очков не больше N/2 1. Во второй и третьей группах результат равен (N 1)/2. Отсюда следует, что вторую группу составляют странные, первую сильные, третью средние, а четвертую слабые. При этом число странных равно [N/2] L, и за счет выбора L его можно сделать любым натуральным числом в пределах от 1 до [N/2] 1. 5. а) Рассмотрим 'среднеарифметического' сильного игрока (т.е. сложим очки, набранные сильными, и разделим на число таких участников). Этот условный игрок выиграл у стольких же сильных, скольким и проиграл. При этом он

проиграл всем странным. Поэтому сумма очков 'среднеарифметического' сильного игрока не больше, чем число средних и слабых плюс половина числа сильных. Аналогично, результат 'среднеарифметического' странного игрока не меньше, чем число сильных плюс половина числа странных. Но эта сумма меньше, чем в первом случае. Как следствие, общее число средних и слабых больше, чем половина общего числа сильных и странных. А это и означает, что сильные и странные составляют менее двух третей от всего состава игроков. Утверждение о численности странных вместе со слабыми доказывается аналогично. б) Построение примера по существу содержится в решении п. а). Разделим участников турнира на три группы, причем в первых двух по [N/3] + 1 человек. Пусть игроки первой группы выиграли все матчи у игроков второй группы. Аналогично, вторая группа выиграла у третей, а третья у первой. Внутри каждой группы все матчи закончились вничью. Нетрудно убедиться, что третья группа состоит из странных, первая из сильных и вторая из слабых. Как и в задаче 4б), здесь можно построить пример, когда количество странных равно произвольно заданному числу, которое не превосходит максимально возможного. Предоставляем вам сделать это самостоятельно. 6'. Если на турнире не было ничьих, то число очков каждого участника целочисленное, в промежутке от 0 до N 1. Если все они различны, то это все целые числа от 0 до N 1. Очевидно, игрок с N 1 очками выиграл у всех остальных. Тогда игрок с N 2 очками выиграл у всех, кроме первого, и т.д. 7. а) Пусть число игроков нечетно, они занумерованы от 1 до 2М + 1 и меньшие номера выиграли у больших со следующими исключениями. Вничью сыграли первый с М-м и (М + + 2)-й с последним. Игрок с номером М + 1 выиграл у всех предыдущих и проиграл всем последующим. Нетрудно убедиться, что сумма очков убывает с ростом номера и (М + + 1)-й игрок странный. б) Нам потребуется следующая Лемма. Пусть в круговом турнире все N участников набрали различное число очков и сделали ровно одну ничью. Тогда: 1) разность соседних результатов не может быть больше 2; 2) если разность соседних результатов равна 2, то игроки не участвовали в ничьей. Доказательство леммы. Пусть лемма неверна. Выберем турнир с наименьшим числом участников, в котором она нарушается. Очевидно, N > 2. Для краткости вместо 'разность соседних результатов' будем говорить просто 'разность'. Пусть S сумма всех разностей, D разность, нарушающая 1) и 2). Число полуцелых разностей среди остальных игроков обозначим K. Каждая полуцелая разность не меньше 1/2, а целая не меньше 1. Поэтому

S D + N - 2 - K 2.

()

Результаты участников ничьей полуцелые, а остальных целые. Поэтому в каждой полуцелой разности обязательно 'участвует' один из тех, кто сделал ничью, и число таких разностей не больше 4. Пусть нарушено 1), т.е. D > 2. Если D 3 , то ввиду () S N 1 (поскольку K 4 ). Если же D = 5/2, то K 3 (так как D полуцелое), и опять S N 1. Пусть теперь нарушено 2), т.е. D = 2 и один из 'участников' этой разности участвовал в ничьей. Его результат полуцелый, поэтому второй 'участник' разности D тоже имеет полуцелый результат и участвовал в ничьей. Отсюда K 2 , и ввиду () снова S N 1. Итак, во всех случаях разность между наилучшим и наихудшим результатами не меньше N 1. Но больше она и не бывает, а равенство означает, что один из участников у всех выиграл, а другой всем проиграл. В разности D не участвует хотя бы один из 'крайних' игроков. Удалим его из турнир-