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

МАТЕМАТИЧЕСКИЙ К МАТЕМАТИЧЕСКИЙ Р У Ж О К КРУЖОК

39

Жеребьевка для чемпиона
Б.ФРЕНКИН

П

соревнованием болельщики поглощены вопросом: кто станет победителем? Ответ зависит от класса игры участников, в какой-то мере и от везения. А когда участников больше двух, то вмешивается такой мощный фактор, как система организации турнира. Два крайних (и наиболее типичных) вида турниров круговой и кубковый (олимпийский). При круговой системе каждый участник играет с каждым. Чемпион определяется по сумме очков, и это звание могут разделить несколько человек. При розыгрыше кубка участники разбиваются на пары по жребию. Те, кто победил в парах, снова составляют пары по жребию, и т.д. Если в очередном туре оказалось нечетное число участников, то один из них пропускает этот тур и сразу выходит в следующий. Ничьи при розыгрыше кубка невозможны. В итоге 'на ковре' остается один спортсмен он и получает кубок. Ясно, что результат кругового турнира меньше подвержен случайностям и надежнее характеризует силы участников. Но при розыгрыше кубка игрок должен все время 'выкладываться', тогда как в круговом турнире важна лишь общая сумма очков. Поэтому кубковые матчи проходят в целом интереснее, чем встречи в круговых чемпионатах. Результаты двух описанных видов соревнований с одним и тем же составом участников могут сильно разли-

ЕРЕД КАЖДЫМ СПОРТИВНЫМ

чаться. Конечно, если дважды провести круговой турнир, то, скорее всего, итог тоже изменится. Но нас интересует влияние самой системы розыгрыша. Поэтому примем предположение о стабильной игре: в каждой паре игроков победитель всегда один и тот же (т.е. если один из игроков в паре хоть раз победил другого, он побеждает его всегда). Тогда ничьи в круговом турнире исключены, поскольку их не бывает в кубковом. (Однако допускается, что один игрок выигрывает у другого, другой у третьего, а при этом третий выигрывает у первого.) В предположении о стабильной игре результаты кругового турнира предопределены в том числе, кто станет чемпионом. (Мы будем называть чемпионами всех, кто разделил первое место.) С кубком дело обстоит иначе: на его судьбу влияет жеребьевка. Конечно, если чемпион кругового турнира выигрывает у всех остальных игроков, то он возьмет кубок при любой жеребьевке. Но если он проиграл хоть одному участнику и жребий свел их в розыгрыше кубка, то для чемпиона все на этом и закончится. Естественно возникает вопрос: возможен ли такой расклад игроков по результатам встреч в парах, что чемпион кругового турнира не выиграет кубок ни при какой жеребьевке? (Примем пока, что пропускать туры никому не приходится. Это значит, что число участников является степенью двойки.) Рассмотрим сначала более про-

стую задачу: А. Прошел чемпионат по круговой системе с участием 2N игроков. Теперь тем же спортсменам предстоит разыграть кубок. Выполнено предположение о стабильной игре. Докажите, что существует жеребьевка розыгрыша кубка, при которой чемпион кругового турнира выйдет в финал. Результат неплохой, но какой-то половинчатый и потому наводит на некие мысли. Оказывается, мысли эти возникают не зря (хотя путь от второго места к первому нелегок!): Б. При тех же условиях докажите, что существует жеребьевка, при которой чемпион кругового турнира получит кубок. Утверждение А, конечно, следует из утверждения Б. Но его стоило установить как отдельный факт: оно доказывается не только гораздо проще, но и принципиально другим способом. Для полноты картины осталось выяснить следующий вопрос: В. Пусть число игроков не является степенью двойки, остальные условия сохраняются. Если в очередной тур розыгрыша кубка вышло нечетное число спортсменов, то один из них по жребию пропускает этот тур и выходит в следующий. Останутся ли верными утверждения А и Б? Автор приведенных задач К.Е.Фельдман. Задача Б была предложена на зимних соревнованиях по отбору на международную олимпиаду 1994 года и оказалась на практике крепким орешком ее решили всего три человека. Мы видим, что простые и всем знакомые ситуации могут служить источником логических задач. Для их решения не требуется применять какие-то сложные теоремы, но сообразительность нужна не меньше, чем в алгебре или геометрии. Возможно, и вам удастся в самой обычной ситуации найти спрятанную в ней головоломку. Желаем успеха!

лев, Юлия Могилат и студентка Марина Хомякова; по секции прикладной математики студенты Виктор Куницын (Санкт-Петербург), Илона Вертинская и Иван Рожнов (Минск), школьники из Санкт-Петербурга Наталия Баранова, Виктория Алавердова и Александр Зимин, а также школьники из белорусского города Осиповичи Андрей Широкий и Андрей Жигадло; по секции теоретической и эксперимен-

тальной физики петербуржец Николай Клишин и москвич Алексей Добрынин. В 2001 году Оргкомитет планирует провести VI Международную конференцию молодых ученых памяти С.Н.Бернштейна и приглашает принять в ней участие старшеклассников и студентов младших курсов (возраст участников не более 19 лет). Полный текст доклада и заявку (в заявке укажите номер факса для отправки приглашения) следует выслать до 10 января 2001 года.

Наш адрес: 199155 Санкт-Петербург, пер.Каховского, 9, Оргкомитет VI Международной конференции памяти С.Н.Бернштейна. Телефон: (812) 350-10-76. Факс: (812) 584-43-43. И.Чистяков