Страница 1 из 1

Строгие турниры

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

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

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

Re: Строгие турниры

Добавлено: 05 май 2014, 15:10
Dendr
Эх... столько писал решение, а потом разавторизовался и не отправилось.

У меня получилось в первой задаче, что ддопустимое место Пупкина <= (n-3)/2.
(вплоть до n=5 доказано,для n=6 и 7 проверено; даже табличка для M=2, n=7 составилась)

Re: Строгие турниры

Добавлено: 06 май 2014, 20:41
Dendr
Строгое решение.

Вариант, когда Пупкин обыграл всех и занял первое место - тривиален. Посмотрим, что будет, если кто-то обойдет его в таблице турнира.

Лемма 1. Если Пупкин может занять (при соблюдении всех условий) M место при n участниках, то то же верно и для n+1 участника.
Доказательство. Пусть состоялись игры между n участниками, включая Пупкина. Приходит некто Шлюпкин и проигрывает всем, заняв последнее место. Порядок остальных участников не изменился, но количество очков у них увеличилось на 1, как и число побед. У Пупкина по-прежнему больше побед, чем у каждого из остальных, и у всех число очков разное. ЧТД
Понятно теперь, что если мы "подобрали" M для какого-то n, то оно подходит и для больших n.

Лемма 2. Лидер строгого турнира победил в по меньшей мере половине матчей.
Пусть победитель набрал X очков, тогда в сумме у всех участников X+(X-0.5)+...+(X-(n-1)/2)>=n(n-1)/2. Следовательно, X>=3(n-1)/4.
Если у победителя турнира w побед, то максимум его очков (все остальные - ничьи) - w+(n-1-w)/2=w/2+(n-1)/2>=3(n-1)/4. Или w>=(n-1)/2. ЧТД

Пусть победитель выиграл w игр и проиграл l. Тогда он набрал w+(n-1-w-l)/2=(n+w-1-l)/2 очков.
Пупкин выиграл по меньшей мере (w+1) игру, т.е. набрал не меньше (w+1) очка.
Наибольший разрыв между победителем и Пупкиным, по очкам, будет при условии, что у Пупкина ровно w+1 очко, а l=0. Разрыв этот равен d=(n-3-w)/2.

Из Леммы 2 следует, что d<=(n-3-n/2+0.5)/2=(n-5)/4. Другими словами, количество участников, обогнавших Пупкина по очкам, <=(n-5)/2, поэтому место, занятое Пупкиным, определяется неравенством M<=(n-3)/2. Это и есть ответ. В том числе, здесь "экспериментально" подтверждена Лемма 1.

Полный ответ: при n<=6 Пупкин может занимать только первое место, при больших - допустимое место определено неравенством M<=(n-3)/2.

Пример для n=7: (M=2, w=3)
здесь + - победа, - - поражение, = - ничья, # - диагональная клетка, W - победитель, P - Пупкин. Таблицу можно всегда скомпоновать "на ходу", используя здравый смысл и предварительную табличку набранных очков.
W #+===++ (+3=3-0; 4.5)
P -#-++++ (+4=0-2; 4)
3 =+#--++ (+3=1-2; 3.5)
4 =-+#-=+ (+2=2-2; 3)
5 =-++#-- (+2=1-3; 2.5)
6 ---=+#= (+1=2-3; 2)
7 ----+=# (+1=1-4; 1.5)

Re: Строгие турниры

Добавлено: 07 май 2014, 13:13
Dendr
Вторая задача: n=18.

На вторую приводить полное аналитическое решение места не хватит, поэтому только основные моменты и выводы.
Если некто занимает k-е место в таблице, то он не занял ни первого, ни последнего места (иначе турнир нестрогий), тогд ниже него (n-k) игроков, выше - (k-1). Зная, что он набрал S очков, мы можем определить максимум очков, набранных теми, кто ниже него (S-0.5)+(S-1)+...
Так же можно определить максимум очков, набранных теми, кто выше (между собой - константа, против данного - определено S, c остальными - чисто победа)
Итак, мы составили f(n, k) - максимум очков, набранных всеми игроками турнира. Это, очевидно, не может быть меньше n(n-1)/2 (иначе никакое другое распределение очков, а значит, сам турнир невозможен). Получаем неравенство f(n, k)>=n(n-1)/2. Если n, k - натуральные, то отсюда можно вывести, что k>=(n+3)/3 - наинизшее место, занятое нашим игроком.
Негатив таблицы дает наивысшее положение "ничейника", которое определяется как k<=2n/3.

Итого - в строгом турнире игрок со всеми ничьими может занимать места из промежутка: n/3+1<=M<=2n/3.

Если Бендер играл так 6 лет подряд, постепенно поднимаясь в таблице, то минимальное n=18, при этом он поднялся с 12 до 7 позиции. Примечательно, что при n=19, по этой теории, так бы не вышло, только 5 лет подряд..

Пример для n=18, M=7 может быть такой:
Есть две подгруппы, в первой (А) 6 участников, во второй (Б) - 11. При перекрестных встречах А побеждал Б всегда.
Внутри подгрупп сложилось так, что в А победитель обыграл всех, занявший 2-е место - всех, кроме победителя и т.д. (т.е., они набрали от 11.5 до 16.5 очков с шагом в 1)
В подгруппе Б участники сыграли так, что победитель набрал 7.5 очков, проигравший - 2.5, остальные - равномерно среди них распределились. Такое распределение ничему не противоречит, и его составить несложно каким угодно.
Ну теперь и появляется затем Бендер, играет со всеми вничью, набирая 8.5 очков (меньше аутсайдера группы А) и принося лидеру группы Б 8 очков в сумме, то есть сохраняя турнир строгим.
12-е место - та же таблица, но все победы инвертированы. Соответственно, промежутки тоже допустимы.

Re: Строгие турниры

Добавлено: 07 май 2014, 13:14
Dendr
Можно было бы еще и с футбольным "Газмясом" рассмотреть турниры, а то и с хоккейным (где правила начисления совсем другие), но с меня хватит.

Re: Строгие турниры

Добавлено: 08 май 2014, 16:04
Юляша
Да, при 16 участниках не получается.

При 6 месте ОБ он и те кто выше набирают вместе как минимум 110 очков; 5 нижних набирают 10 очков между собой + 2,5 приходят от ОБ. Итого 110+10+2,5=122,5>120 доступных.