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


Содержание

ММ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 балла

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

 

 


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

marathon/problem_48.txt · Последние изменения: 2016/03/26 14:20 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006