=====ММ48=====

**Конкурсная задача ММ48** (7 баллов)

Игоговую таблицу однокругового шахматного турнира будем называть "строгой", если никакие два участника не имеют поровну очков. Турнир с строгой таблицей также будем называть "строгим".

1) Гросмейстер Грустин Попалов выиграл в строгом турнире больше партий, чем каждый из других участников. На каком месте мог он оказаться в итоге, если в турнире участвовало n шахматистов?
(2 балла)

2) Гроссмейстер Любомир Миролюбоевич шесть лет подряд играл в однокруговых рождественских турнирах в городе Зейк-ан-Вее. Каждый год он завершал все свои партии вничью, но год от года занимал все более высокое место. В каждом турнире было n участников и все они были строгие. При каком наименьшем n возможна такая ситуация?
(2 балла)

3) Обозначим через d(n) количество мест, которые может занять Миролюбов, сыграв вничью, все партии строгого турнира при n участниках.
Найти явное выражение для d(n). (3 балла)

**Решение**

Примем (вслед за Олегом Полубасовым, а также шахматными профессионалами) новую систему начисления очков:\\
за победу будем давать 1 очко;\\
за ничью - 0 очков;\\
за поражение - -1 очко.\\
Ясно, что Sn (число очков, набранных участником по новой системе) связано с So (его суммой очков по традиционной системе) соотношением Sn = 2So-n+1, где n - количество участников турнира. Поэтому места, занятые ГП, ЛМ (и остальными участниками турнира) при переходе на новую систему не изменятся. Но зато мы избавимся от дробей и получим постоянную (не зависящую от числа участников) сумму очков всех участников. Эта сумма всегда будет равняться 0 (так же как и количество очков, набранных ЛM).

48.1

Ясно, что для определения возможных мест ГП надо найти наихудшее из них.

Выясним, какое наименьшее число очков мог набрать победитель строгого турнира.

Пусть сначала n = 2k+1. Тогда, располагая участников в итоговой таблице максимально плотно, получим, что у победителя не менее k очков.\\
Если же n = 2k, то расположить участников в итоговой таблице "без дыр" нельзя. Приходиться допустить один пропуск в середине таблицы, а в остальном вновь расставить очки максимально плотно. Получается, что и в этом случае у победителя как минимум k очков, а значит и не менее k побед.

Тогда у ГП не менее k+1 побед. (Здесь мы предполагаем, что победитель и ГП - разные лица. Ясно, что при малых n такая ситуация невозможна. Но с этими случаями мы легко разберемся отдельно.)\\
Допустим, что остальные n-1-(k+1) партий ГП проиграл. Тогда он набрал 2 очка при нечетном n и 3 очка - при четном.\\
В первом из этих случаев ГП пропустил вперед себя k-2 участников и занял k-1 -е место. В случае четного n место ГП не ниже k-2.\\
Возвращаясь к n и объединяя случаи, делаем вывод, что место ГП не ниже [(n-3)/2] ([x]- целая часть x).

Если допустить, что победитель турнира набрал хотя бы на очко больше, то результат ГП увеличится сразу на 2 очка и его место будет выше. Тем самым, доказано, что ГП не может занять место ниже [(n-3)/2].

Покажем теперь, что место [(n-3)/2] достижимо.

Соответствующий турнир для n = 2k+1 построим так:\\
1) ГП проиграл k-1 партию лидерам (худший из них занял место на одно ниже места ГП) и выиграл k+1 партию у аутсайдеров;\\
2) Участники, опередившие ГП, выиграли у аутсайдеров, отставших от них не менее, чем на k+2 места;\\
3) участник, расположившийся в середине турнирной таблицы, выиграл у участника, занявшего последнее место;\\
4) Остальные встречи завершились вничью.

Вот пример итоговой таблицы для n = 11:

|Х |= |= |+ |= |= |= |+ |+ |+ |+ | 5|
|= |Х |= |+ |= |= |= |= |+ |+ |+ | 4|
|= |= |Х |+ |= |= |= |= |= |+ |+ | 3|
|- |- |- |Х |- |+ |+ |+ |+ |+ |+ | 2 (ГП)|
|= |= |= |+ |Х |= |= |= |= |= |= | 1|
|= |= |= |- |= |Х |= |= |= |= |+ | 0|
|= |= |= |- |= |= |Х |= |= |= |= |-1|
|- |= |= |- |= |= |= |Х |= |= |= |-2|
|- |- |= |- |= |= |= |= |Х |= |= |-3|
|- |- |- |- |= |= |= |= |= |Х |= |-4|
|- |- |- |- |= |- |= |= |= |= |Х |-5|

Для n = 2k правила построения таблицы немного иные:\\
1) ГП проиграл k-2 партии лидерам (худший из них занял место на одно ниже места ГП) и выиграл k+1 партию у аутсайдеров;\\
2) Участники, опередившие ГП, выиграли у аутсайдеров, отставших от них не менее, чем на k+1 место;\\
3) участник, расположившийся следом за ГП, выиграл у участника, занявшего последнее место;\\
4) участник, занявший k-е место, выиграл у участников, занявших последнее и предпоследнее места;\\
5) Остальные встречи завершились вничью.\\

Вот пример итоговой таблицы для n = 12:

|Х |= |= |+ |= |= |= |+ |+ |+ |+ |+ | 6|
|= |Х |= |+ |= |= |= |= |+ |+ |+ |+ | 5|
|= |= |Х |+ |= |= |= |= |= |+ |+ |+ | 4|
|- |- |- |Х |- |+ |+ |+ |+ |+ |+ |+ | 3 (ГП)|
|= |= |= |+ |Х |= |= |= |= |= |= |+ | 2|
|= |= |= |- |= |Х |= |= |= |= |+ |+ | 1|
|= |= |= |- |= |= |Х |= |= |= |= |= |-1|
|- |= |= |- |= |= |= |Х |= |= |= |= |-2|
|- |- |= |- |= |= |= |= |Х |= |= |= |-3|
|- |- |- |- |= |= |= |= |= |Х |= |= |-4|
|- |- |- |- |= |- |= |= |= |= |Х |= |-5|
|- |- |- |- |- |- |= |= |= |= |= |Х |-6|

Легко видеть, что ГП может занять любые места выше [(n-3)/2]. Заменив в турнирной таблице поражение ГП от участника, расположившегося в турнирной таблице непосредственно над ГП, на ничью, мы можем поменять их местами в итоговой таблице. Продолжая в том же духе, можно поднимать ГП вплоть до первого места.

Заметим, наконец, что если число участников строгого турнира не превосходит шести, то ГП не может опуститься ниже первого места.

Ответ: При n < 7 ГП занимает первое место, при n > 6 ГП может занять любое место в диапазоне [1 .. [(n-3)/2].

48.2

Ответ к этому пункту - n = 18.\\
Это вытекает из решения 48.3

48.3

Пусть ЛМ занял наиболее низкое из доступных ему мест и при этом пропустил вперед k соперников (лидеров). Допустим также, что эти k лидеров выиграли все свои партии у участников позади ММ (аутсайдеров).\\
Во встречах между собой лидеры в сумме набрали 0 очков, а во встречах с аутсайдерами (n-k-1)k очков. Ясно, что это количество очков не может быть меньше суммы 1+2+3+...+k - минимально возможной суммы участников, опередивших ЛМ, набравшего 0 очков.\\
Таким образом, nk - k2 - k >= k(k+1)/2, откуда k <= [2n/3] - 1.\\
Значит, позади ЛМ останутся не менее n - [2n/3] участников.\\
Из соображений симметрии впереди ЛМ расположатся также менее n - [2n/3] участников. Поэтому d(n) не может превышать 2[2n/3] - n мест.

Докажем, что весь этот диапазон достижим.

Для этого покажем, что для любого нечетного числа n = 2k+1 участников существует плотный строгий турнир с распределением очков:\\
k, k-1, k-2, ... 1, 0, -1, ..., -(k-2), -(k-1), -k. Для построения такого турнира достаточно придерживаться следующих правил:\\
1) участники, абсолютная величина разности мест которых отличается не более, чем на k, разошлись миром;\\
2) в остальных встречах победу одержал тот из соперников, кто в итоге занял более высокое место.

Для четных n = 2k плотных турниров не существует, но зато есть почти плотные строгие турнир с распределением очков:\\
k, k-1, k-2, ... 1, -1, ..., -(k-2), -(k-1), -k.
Правила их построения таковы:\\
1) участники, абсолютная величина разности мест которых отличается менее, чем на k, разошлись миром;\\
2) в остальных встречах победу одержал тот из соперников, кто в итоге занял более высокое место.

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

Приведем пример итоговой таблицы такого турнира для n = 18, в котором ММ займет наиболее низкое место:

|X |= |= |= |= |= |+ |+ |+ |+ |+ |= |+ |+ |+ |+ |+ |+ | 11|
|= |X |= |= |= |= |= |+ |+ |+ |+ |= |+ |+ |+ |+ |+ |+ | 10|
|= |= |X |= |= |= |= |= |+ |+ |+ |= |+ |+ |+ |+ |+ |+ | 9|
|= |= |= |X |= |= |= |= |= |+ |+ |= |+ |+ |+ |+ |+ |+ | 8|
|= |= |= |= |X |= |= |= |= |= |+ |= |+ |+ |+ |+ |+ |+ | 7|
|= |= |= |= |= |X |= |= |= |= |= |= |+ |+ |+ |+ |+ |+ | 6|
|- |= |= |= |= |= |X |= |= |= |= |= |+ |+ |+ |+ |+ |+ | 5|
|- |- |= |= |= |= |= |X |= |= |= |= |+ |+ |+ |+ |+ |+ | 4|
|- |- |- |= |= |= |= |= |X |= |= |= |+ |+ |+ |+ |+ |+ | 3|
|- |- |- |- |= |= |= |= |= |X |= |= |+ |+ |+ |+ |+ |+ | 2|
|- |- |- |- |- |= |= |= |= |= |X |= |+ |+ |+ |+ |+ |+ | 1|
|= |= |= |= |= |= |= |= |= |= |= |X |= |= |= |= |= |= | 0 (ЛМ)| 
|- |- |- |- |- |- |- |- |- |- |- |= |X |= |= |+ |+ |+ |-8|
|- |- |- |- |- |- |- |- |- |- |- |= |= |X |= |= |+ |+ |-9|
|- |- |- |- |- |- |- |- |- |- |- |= |= |= |X |= |= |+ |-10|
|- |- |- |- |- |- |- |- |- |- |- |= |- |= |= |X |= |= |-12|
|- |- |- |- |- |- |- |- |- |- |- |= |- |- |= |= |X |= |-13|
|- |- |- |- |- |- |- |- |- |- |- |= |- |- |- |= |= |X |-14|

Ответ: d(n) = 2[2n/3] - n

**Oбсуждение**

По-видимому, я недооценил пункт 48.1.\\
Составляя задачу 48, я сначала придумал 2-й и 3-й пункты и достаточно много повозился с ними, прежде чем решил. 1-й пункт я придумал уже тогда, когда "кухня" строгих турниров была мне близка и понятна.\\
Наверное, именно этим объясняется, что 48.1 я решил с ходу.\\
Оформляя же решение и разбирая решения, присланные участниками марафона, я понял, что поскупился. Это позднее прозрение повлияло на распределение призовых баллов.

Отмечу, что, в отличие от формулы в 48.1, формула d(n) = 2[2n/3] - n возвращает верные значения, начиная с наименьшего осмысленного n = 2. Нули, возвращаемые этой формулой для n = 2 и n = 4, показывают, что для этих значений n строгих турниров с участием ЛМ не существует.

Любопытно, что все три марафонца, откликнувшиеся на эту задачу, привели внешне различные формулы для d(n):\\
Андрей Богданов - ту же, что приведена в решении;\\
Андрей Винокуров - n - 2ceil(n/3) (где ceil(x) - потолок x);\\
Олег Полубасов - |n - 2[(n+2)/3]|. Знак абсолютной величины добавлен, чтобы ответ подходил и для "турнира" из одного участника.

Андрей Винокуров интересовался, зачем в задачу включен пункт 48.2, решение которого вытекает из решения 48.3.\\
Этот пункт был добавлен для тех марафонцев, которые вполне могли справится с ним, даже не осилив 48.3. То, что это возможно, показывает пример школьников, которым я давал оба пункта и которые справились (с некоторой потерей строгости) только с 48.2.

**Награды**

Как я и обещал, отвечая Андрею Винокурову в RU.MATH, за правильное решение 48.1 и 48.3, снабженное строгими доказательствами существования подходящих таблиц, я начислил баллов больше, чем заявлено в цене задачи.\\
С учетом этого Андрей Богданов и Олег Полубасов получают по 10 призовых баллов, а Андрей Винокуров (написавший целый трактат по теории правильных турниров) - 12 призовых баллов.

**Эстетическая оценка задачи - 3.8 балла**

Отмечу, что уменьшение (надеюсь, временное) числа марафонцев, ответивших на задачу, не уменьшило диаметральности их мнений в оценивании эстетической стороны задачи. Наверное, единодушие будет достигнуто лишь тогда, когда какую-то из задач решит лишь один марафонец ;)
Но я надеюсь, что такой ситуации не случится.