Конкурсная задача №70 (12 баллов)
В k-круговом шахматном блицтурнире приняли участие n шахматистов.
В итоговой таблице никакие два участника не набрали поровну очков (т.е.
в терминах задачи 48 турнир оказался строгим).
На торжественном закрытии турнира участник, занявший последнее место,
заметил, что, если бы очки начислялись так же как в футболе, он занял бы
не последнее, а первое место.
Более того, при подсчете очков по футбольным правилам, никакие два участника
по-прежнему не имели бы поровну очков, но при этом выстроились бы в итоговой
таблице в обратном порядке.
1. Какое наименьшее число партий могло быть сыграно в таком турнире?
2. При каком наименьшем k возможна описанная ситуация?
3. При каком наименьшем n достигается наименьшее k, при котором возможна
такая ситуация.
Примечания:
В k-круговом турнире каждый участник встречается с каждым k раз.
За победу в партии в шахматном турнире начисляется одно очко, за ничью
пол-очка, а за поражение ноль очков.
За победу в матче в в футбольном турнире начисляется три очка, за ничью
одно очко, а за поражение ноль очков.
Разумеется, в турнире участвует более одного шахматиста.
Решение
Турниры, о которых идет речь в условии задачи будем называть «перевертышами».
Для удобства будем считать, что за победу шахматист получает 2 очка,
а за ничью - 1. Такую систему подсчета очков будем называть «старой»,
а футбольную (3 очка за победу) - «новой». Места команд (если иное не оговорено
особо) будем называть по старой системе.
Лемма: k>5
Пусть участник A выиграл v, свел вничью s и проиграл d партий.
Тогда участник В, отставший от него на одно очко по старой системе
и опередивший на одно очко по новой, должен был выиграть v+2, сыграть
вничью s-5 и проиграть d+3 партии.
Даже если предположить, что все участники расположились в турнирных таблицах
(и по старой, и по новой системе) максимально плотно, и, что у последнего
совсем нет ничьих, у первого все равно должно быть не менее 5*(n-1) ничьих.
Общее число партий, сыгранных одним участником равно k*(n-1). Участник,
занявший первое место не мог завершить все партии вничью, поэтому
k*(n-1) > 5*(n-1), т.е. k>5.
1. 30 партий.
Ясно, что «турнир» из двух участников не может быть перевертышем.
Из леммы следует, что при n>3 в турнире перевертыше должно быть не менее
C(n,4)*6 = 36 партий.
При n = 3 существует турнир-перевертыш из 10 кругов и 30 партий.
Вот его итоговая таблица:
| 1 | 2 | 3 | Пб | Нч | Пр | O1 02 |
1. | XXXXXXX | +0=10-0 | +3=5-2 | 3 | 15 | 2 | 21 24 |
2. | +0=10-0 | XXXXXXX | +5=0-5 | 5 | 10 | 5 | 20 25 |
3. | +2=5-2 | +5=0-5 | XXXXXXX | 7 | 5 | 8 | 19 26 |
Менее чем 10 кругов в турнире-перевертыше из трех команд быть не может.
В самом деле, победитель должен была сыграть вничью, по крайней мере,
на 5 партий больше, чем второй. Сделать 5 лишних ничьих он мог только с
аутсайдером. Но у участника, занявшего второе место должно быть на 5
ничьих больше, чем у аутсайдера. Поэтому первый и второй призеры должны были
сыграть между собой вничью не менее 10 раз и, значит, в турнире не менее
10 кругов.
2. k = 6.
Из леммы следует, что меньше 6 кругов в турнире-перевертыше быть не может.
Приведем таблицу 6-крувого турнира-перевертыша:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Пб | Нч | Пр | О1 О2 |
1. | XXXX | +0=6 | +0=6 | +0=6 | +0=6 | +0=6 | +1=5 | +1=5 | +1=5 | +1=5 | +1=5 | 5 | 55 | 0 | 65 70 |
2. | +0=6 | XXXX | +0=6 | +0=6 | +0=6 | +0=6 | +1=5 | +1=5 | +1=5 | +1=5 | +3=0 | 7 | 50 | 3 | 64 71 |
3. | +0=6 | +0=6 | XXXX | +0=6 | +0=6 | +0=6 | +1=5 | +1=5 | +1=5 | +3=0 | +3=0 | 9 | 45 | 6 | 63 72 |
4. | +0=6 | +0=6 | +0=6 | XXXX | +0=6 | +0=6 | +1=5 | +1=5 | +3=0 | +3=0 | +3=0 | 11 | 40 | 9 | 62 73 |
5. | +0=6 | +0=6 | +0=6 | +0=6 | XXXX | +0=6 | +1=5 | +3=0 | +3=0 | +3=0 | +3=0 | 13 | 35 | 12 | 61 74 |
6. | +0=6 | +0=6 | +0=6 | +0=6 | +0=6 | XXXX | +3=0 | +3=0 | +3=0 | +3=0 | +3=0 | 15 | 30 | 15 | 60 75 |
7. | +0=5 | +0=5 | +0=5 | +0=5 | +0=5 | +3=0 | XXXX | +3=0 | +3=0 | +4=0 | +4=0 | 17 | 25 | 18 | 59 76 |
8. | +0=5 | +0=5 | +0=5 | +0=5 | +3=0 | +3=0 | +3=0 | XXXX | +3=0 | +3=0 | +4=0 | 19 | 20 | 21 | 58 77 |
9. | +0=5 | +0=5 | +0=5 | +3=0 | +3=0 | +3=0 | +3=0 | +3=0 | XXXX | +3=0 | +3=0 | 21 | 15 | 24 | 57 78 |
10 | +0=5 | +0=5 | +3=0 | +3=0 | +3=0 | +3=0 | +2=0 | +3=0 | +3=0 | XXXX | +3=0 | 23 | 10 | 27 | 56 79 |
11 | +0=5 | +3=0 | +3=0 | +3=0 | +3=0 | +3=0 | +2=0 | +2=0 | +3=0 | +3=0 | XXXX | 25 | 5 | 30 | 55 80 |
3. n = 11.
В предыдущем пункте приведена таблица 6-крувого турнира-перевертыша с 11
участниками. Покажем, что при меньших n, 6-крувого турнира-перевертыша
не существует.
Отдельно рассмотрим случаи четного и нечетного n.
1) n = 2s+1.
Каждый участник сыграл по 12s партий.
В этом случае возможен плотный (когда соседей по таблице отделяет друг от
друга одно очко) 6-круговой турнир. В таком турнире у победителя 13s, а
у аутсайдера 11s очков.
Пусть аутсайдер такого турнира сыграл вничью x партий.
Тогда участник, занявший предпоследнее место - x+5 партий;
участник, занявший третье с конца место - x+10 партий;
……………………….
победитель - x+10s партий.
Для того чтобы набрать 13s очков, победитель должен выиграть не менее s партий.
Поэтому 12s-(x+10s) ≥ s, откуда x ≤ s.
Кроме того, числа x и s должны быть одной четности (иначе в общее число ничьих
в турнире не будет целым).
Просуммируем ничьи, сделанные первыми s участниками:
(x+5s+5) + (x+5s+10) + … + (x+10s) = s*(2x+15s+5)/2.
Допустим, что первые s участников сыграли все партии между собой вничью.
Это составит 6s*(s-1) ничьих.
Тогда a = s*(2x+15s+5)/2 - 6s*(s-1) = s*(3*s+2x+17)/2 приходится на ничьи,
сыгранные s лидерами с остальными участниками. Ясно, что это число
не должно превышать общего количества ничьих участников, занявших места с
s+1-го по последнее,
т.е. b = x + (x+5) + … + (x+5s) = (2x+5s)*(s+1)/2.
Иными словами, b-a = s2 - 6s + x должно быть неотрицательно.
Ясно, что это невозможно при s<5 (напомню, что x ≤ s).
Впервые b-a становится неотрицательным при s = x = 5, что, как раз,
соответствует приведенному выше примеру.
Ясно, что, если турнир-перевертыш не является плотным (хотя бы по одной из
систем), то минимальное s, которое в приведенном примере достигается «впритык»,
может только увеличиться.
2) n = 2s.
В этом случае, турнир не может быть плотным по старой системе. В самом деле,
если бы турнир был плотным, один из участников набрал бы ровно половину
возможных очков - n-1. Но тогда по соображениям симметрии для каждого
участника, набравшего n-1+x очков, найдется участник, набравший n-1-x очков.
Но это противоречит четности числа участников.
Итак, в итоговом положении турнира-перевертыша с четным числом участников
должен быть хотя бы один просвет в 2 очка (между участниками, занявшими
s-е и s+1-е места). Этот просвет отвечает скачку в 8 ничьих, т.е. участника,
набравшего по старой системе на два очка меньше, а по новой - на очко больше,
должно быть на 8 ничьих меньше, на 3 победы и на 5 поражений больше.
Наиболее плотное распределение ничьих (от последнего места к первому):
x, x+5, …, x+5*(s-1), x+5s+3, …, x+10s-7, x+10s-2.
(В этом случае тоже не сложно найти ограничения для x, но они не существенны
для дальнейших рассуждений.)
Как и в предыдущем случае, допустим, что s участников из верхней половины
таблицы завершили все свои партии вничью. Тогда с участниками из нижней
части таблицы они сделали a = (x+5s+3) +…+ (x+10s-7) + (x+10s-2) - 6s*(s-1)
ничьих.
В то же время, последние s участников сделали b = x + (x+5) + … + (x+5s-5)
ничьих.
Учитывая, что b-a = 2s-18 должно быть неотрицательным, получим, что при
четном числе участников в турнире-перевертыше должно быть занято не менее
18 шахматистов.
Замечу (хотя это и не важно для строгости решения), что пример 6-кругового
турнира-перевертыша для 18 участников легко строится.
Обсуждение
Составляя аналог выражения b-a для других k и n и требуя его
неотрицательности, легко получить наименьшие возможные k для всех n
(и наименьшие n для всех k):
n | k |
2 | - |
4 | 13 |
3 | 10 |
6 | 9 |
5, 8 | 8 |
7, 9, 10, 12, 14, 16 | 7 |
11, 13, 15, 17, 18,… | 6 |
Любопытно, что условие неотрицательности b-a, фигурировавшее в наших
рассуждениях, как необходимое для существования турнира-перевертыша,
всякий раз оказывается и достаточным (при подходящих x).
Награды
За правильное решение этой задачи Виктор Филимоненков, Влад Франк, Андрей
Богданов и Олег Полубвсов получают по 12, а Сергей Беляев -11 призовых баллов.
Эстетическая оценка задачи - 4.5 балла