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

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

27

Странные игроки
Б.ФРЕНКИН
Парадоксы турнирных таблиц
Спортивные турниры служат источником множества логических задач. Даже при простой схеме проведения легко возникают необычные ситуации. Пример. Тридцать три богатыря устроили соревнования по борьбе. Каждый боролся с каждым один раз. Победа давала 1 очко, поражение 0, ничьих не было. Один богатырь выступил странно. Он победил всех, кто в итоге набрал больше очков, чем он, и проиграл всем, кто набрал меньше, чем он. Равного с ним количества очков не набрал никто. Докажите, что странный богатырь занял место не выше тринадцатого и не ниже двадцать первого.
Решение. Предположим, что странный богатырь занял место выше тринадцатого. Количество тех, кто набрал меньше очков, превышает двадцать. Рассмотрим их поединки между собой. Каждый из них провел не менее 20 поединков. Кто-то выиграл не менее половины этих поединков и, следовательно, набрал в них не менее 10 очков. Кроме того, он победил странного значит, всего получил не менее 11 очков. Странный богатырь набрал больше его, т.е. не менее 12 очков. Но странный победил только тех, кто выше его в турнирной таблице следовательно, их не менее 12, и странный не мог занять место выше тринадцатого. Поменяем теперь результаты всех матчей на противоположные. Условия задачи по-прежнему выполняются, а последовательность занятых мест изменилась на обратную. Странный богатырь занял теперь место не выше тринадцатого. Остается заметить, что при 33 участниках двадцать первое место это тринадцатое с конца.

Решение. а) Пусть в турнире шесть участников (см. таблицу). Первые трое сыграли между собой вничью, четвертый с пятым также вничью, причем проиграли первым троим, а шестой выиграл у первых трех и проиграл четвертому и пятому. Тогда шестой разделил первое место с первыми тремя игроками и при этом является странным.

Число участников турнира далее обозначаем N. Результат игрока это сумма очков, которую он набрал. Однако такое определение странного игрока имеет некий изъян. А именно, пусть все участники турнира получили поровну. Тогда для каждого из них отсутствуют и набравшие больше, и набравшие меньше. Формально мы можем считать всех игроков странными. Но это само по себе странно, особенно в такой тривиальной ситуации. Поэтому в дальнейшем всегда предполагается, что не все участники турнира набрали одинаковое количество очков. При этом считается допустимым, если никто не набрал больше очков, чем странный игрок. Точно так же ему не запрещается разделить и последнее место.

3 1:1 1: 1 222 1: 1 :1 2 2 22 1 :1 1 :1 3 2222 2

1

4

5

6

11:0 1:0 0:1 2 1 1:01:0 0:1 2
1:0 1:0 0:1

4 0:10:1 0:1 5 0:10:10:1

1:1 22

1 :1 1:0 22
1:0

6 1:01:01:00:1 0:1
Чтобы поместить странного игрока на последнее место, поменяем все результаты на противоположные. б) Пусть первое место полностью принадлежит странным, и их число равно М. Любой из них проиграл всем, кто не делит первое место, и поэтому набрал не более М 1 очков. Игрок, не находящийся на первом месте, выиграл у всех странных и потому получил результат не меньше М, что противоречит предыдущему. Значит, первое место не может принадлежать только странным. Для последнего места рассуждение аналогичное.

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

На любом турнире возможен странный участник вроде такого богатыря. Изучим эту ситуацию подробнее: в ней кроется немало интересного. Итак, странный участник кругового турнира характеризуется тем, что он выиграл у всех, кто набрал больше очков, чем он, и проиграл всем, кто набрал меньше. С теми, кто выступил наравне с ним, такой игрок мог сыграть как угодно. Подразумевается, что турнир проходит в один круг, причем победа дает одно очко, ничья половину, поражение ноль.
7*

Если игрок получил столько же очков, сколько и странные, но сам не является странным, то назовем его средним. Тех, кто набрал больше, будем называть сильными, а тех, кто набрал меньше, слабыми. В какой же части турнирной таблицы располагаются странные? Например: Задача 2. а) Может ли странный игрок разделить первое место? А последнее? б) Могут ли на первом или последнем месте находиться только странные?

Мы видели, что все странные набирают одинаковое количество очков. И не нужно знать исход каждого матча, чтобы определить это количество: Задача 3. Известны результаты всех игроков. Известно также, что на турнире были странные участники. Как определить, сколько очков они набрали?
Решение этой задачи, а также задач 4, 5 и 7 см. в конце журнала.

Обычных всегда большинство. Но не всегда подавляющее
Сколько же может быть на турнире странных участников? Ясно, что все одновременно такими не бывают. Более точно: Задача 4. а) Число странных всегда не больше [N/2] 1. Докажите это.