Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№70

Конкурсная задача №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 221 24
2.+0=10-0XXXXXXX+5=0-5 5 10 520 25
3.+2=5-2 +5=0-5 XXXXXXX7 5 819 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=55 55 065 70
2.+0=6XXXX+0=6+0=6+0=6+0=6+1=5+1=5+1=5+1=5+3=07 50 364 71
3.+0=6+0=6XXXX+0=6+0=6+0=6+1=5+1=5+1=5+3=0+3=09 45 663 72
4.+0=6+0=6+0=6XXXX+0=6+0=6+1=5+1=5+3=0+3=0+3=01140 962 73
5.+0=6+0=6+0=6+0=6XXXX+0=6+1=5+3=0+3=0+3=0+3=013351261 74
6.+0=6+0=6+0=6+0=6+0=6XXXX+3=0+3=0+3=0+3=0+3=015301560 75
7.+0=5+0=5+0=5+0=5+0=5+3=0XXXX+3=0+3=0+4=0+4=017251859 76
8.+0=5+0=5+0=5+0=5+3=0+3=0+3=0XXXX+3=0+3=0+4=019202158 77
9.+0=5+0=5+0=5+3=0+3=0+3=0+3=0+3=0XXXX+3=0+3=021152457 78
10+0=5+0=5+3=0+3=0+3=0+3=0+2=0+3=0+3=0XXXX+3=023102756 79
11+0=5+3=0+3=0+3=0+3=0+3=0+2=0+2=0+3=0+3=0XXXX25 53055 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 балла


 

 


Страница: [[marathon:problem_70]]

marathon/problem_70.txt · Последние изменения: 2016/10/12 10:39 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006