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

Логические задачи

Модераторы: Азарапетыч, Администрация

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

Сообщение Петр Иванович Д. » 03 май 2014, 15:40

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

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

2) Гроссмейстер Остап Бендер шесть лет подряд играл в однокруговых рождественских турнирах в городе Васюки. Каждый год он завершал все свои партии вничью, но год от года занимал все более высокое место. В каждом турнире было n участников и все они были строгие. При каком наименьшем n возможна такая ситуация?
Петр Иванович Д.
Писатель на заборах
Писатель на заборах
 
Сообщения: 120
Зарегистрирован: 29 мар 2012, 18:05

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

Сообщение Dendr » 05 май 2014, 15:10

Эх... столько писал решение, а потом разавторизовался и не отправилось.

У меня получилось в первой задаче, что ддопустимое место Пупкина <= (n-3)/2.
(вплоть до n=5 доказано,для n=6 и 7 проверено; даже табличка для M=2, n=7 составилась)
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Dendr » 06 май 2014, 20:41

Строгое решение.

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

Лемма 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)
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Dendr » 07 май 2014, 13:13

Вторая задача: 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-е место - та же таблица, но все победы инвертированы. Соответственно, промежутки тоже допустимы.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Dendr » 07 май 2014, 13:14

Можно было бы еще и с футбольным "Газмясом" рассмотреть турниры, а то и с хоккейным (где правила начисления совсем другие), но с меня хватит.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Юляша » 08 май 2014, 16:04

Да, при 16 участниках не получается.

При 6 месте ОБ он и те кто выше набирают вместе как минимум 110 очков; 5 нижних набирают 10 очков между собой + 2,5 приходят от ОБ. Итого 110+10+2,5=122,5>120 доступных.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3158
Зарегистрирован: 15 янв 2009, 12:32


Вернуться в Задачки

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1