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

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

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

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

Решение

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

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 - k² - 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 - 2*ceil(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 балла

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