Разделы 
Дополнительно
Задача по математике - 3403
2019-06-03 
На берегу круглого острова Гдетотам расположено 20 деревень, в каждой живет по 20 борцов. Был проведен турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня $А$ считается сильнее деревни $Б$, если хотя бы $k$ поединков между борцами из этих деревень заканчивается победой борца из деревни $А$. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь $k$? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)
Решение:
Приведем пример, показывающий, что при $k \leq 290$ описанная ситуация возможна. Упорядочим всех борцов по силе и перенумеруем их по возрастанию силы (первый - самый слабый). Назовем 210 слабейших новичками, а 190 сильнейших - мастерами. В частности, любой новичок окажется слабее любого мастера. Пронумеруем деревни против часовой стрелки. Поместим в первую деревню одного слабейшего новичка и 19 слабейших мастеров; во вторую - двух новичков, слабейших из оставшихся, и 18 мастеров, слабейших из оставшихся; в третью - трех слабейших из оставшихся новичков и 17 мастеров, слабейших из оставшихся, и т. д.; в последнюю деревню мы поместим 20 сильнейших новичков. Это размещение по деревням указано в таблице (в столбце «Борцы» числа, набранные прямым шрифтом, означают силы мастеров, набранные курсивом - силы новичков).
Покажем, что $i$-я деревня сильнее $(i - 1)$-й при $i > 1$. Действительно, в $i$-й деревне есть $i$ новичков и $20 - i$ мастеров. При этом мастера $i$-й деревни победят всех в $(i - 1)$-й, а новички победят новичков, и всего побед будет $20(20 - i) + i(i - 1) = i^2 - 21i + 400$. Вершина этой параболы находится в точке $i = 10,5$, а ветви направлены вверх, поэтому минимальное значение в целой точке достигается ровно при двух значениях - $i = 10$ и $i = 11$ - и равно $10^2 - 21 \cdot 10 + 400 = 290$. То есть $i$-я деревня сильнее $(i - 1)$-й при $k \leq 290$. Кроме того, мастера первой деревни победят новичков 20-й, и всего побед будет $20 \cdot 19 = 380 > 290$, т. е. все условия выполнены.
Покажем, что при $k > 290$ такая ситуация невозможна. Упорядочим в каждой деревне борцов по убыванию силы и выберем в каждой деревне десятого по силе борца. Покажем, что деревня, в которой живет слабейший из выбранных борцов, не может быть сильнее следующей за ней. Обозначим выбранных борцов в нашей и следующей деревнях через $A$ и $B$ соответственно. Тогда в нашей деревне 11 борцов не сильнее, чем $A$, а в следующей - 10 борцов хотя бы такой же силы, как $B$. Все поединки между этими борцами закончатся в пользу второй деревни, и этих поединков - 110, т. е. поединков, в которых выиграл борец нашей деревни, не больше, чем $20 \cdot 20 - 110 = 290$.
Ответ: 290.
На берегу круглого острова Гдетотам расположено 20 деревень, в каждой живет по 20 борцов. Был проведен турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня $А$ считается сильнее деревни $Б$, если хотя бы $k$ поединков между борцами из этих деревень заканчивается победой борца из деревни $А$. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь $k$? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)
Решение:
Приведем пример, показывающий, что при $k \leq 290$ описанная ситуация возможна. Упорядочим всех борцов по силе и перенумеруем их по возрастанию силы (первый - самый слабый). Назовем 210 слабейших новичками, а 190 сильнейших - мастерами. В частности, любой новичок окажется слабее любого мастера. Пронумеруем деревни против часовой стрелки. Поместим в первую деревню одного слабейшего новичка и 19 слабейших мастеров; во вторую - двух новичков, слабейших из оставшихся, и 18 мастеров, слабейших из оставшихся; в третью - трех слабейших из оставшихся новичков и 17 мастеров, слабейших из оставшихся, и т. д.; в последнюю деревню мы поместим 20 сильнейших новичков. Это размещение по деревням указано в таблице (в столбце «Борцы» числа, набранные прямым шрифтом, означают силы мастеров, набранные курсивом - силы новичков).
Покажем, что $i$-я деревня сильнее $(i - 1)$-й при $i > 1$. Действительно, в $i$-й деревне есть $i$ новичков и $20 - i$ мастеров. При этом мастера $i$-й деревни победят всех в $(i - 1)$-й, а новички победят новичков, и всего побед будет $20(20 - i) + i(i - 1) = i^2 - 21i + 400$. Вершина этой параболы находится в точке $i = 10,5$, а ветви направлены вверх, поэтому минимальное значение в целой точке достигается ровно при двух значениях - $i = 10$ и $i = 11$ - и равно $10^2 - 21 \cdot 10 + 400 = 290$. То есть $i$-я деревня сильнее $(i - 1)$-й при $k \leq 290$. Кроме того, мастера первой деревни победят новичков 20-й, и всего побед будет $20 \cdot 19 = 380 > 290$, т. е. все условия выполнены.
Покажем, что при $k > 290$ такая ситуация невозможна. Упорядочим в каждой деревне борцов по убыванию силы и выберем в каждой деревне десятого по силе борца. Покажем, что деревня, в которой живет слабейший из выбранных борцов, не может быть сильнее следующей за ней. Обозначим выбранных борцов в нашей и следующей деревнях через $A$ и $B$ соответственно. Тогда в нашей деревне 11 борцов не сильнее, чем $A$, а в следующей - 10 борцов хотя бы такой же силы, как $B$. Все поединки между этими борцами закончатся в пользу второй деревни, и этих поединков - 110, т. е. поединков, в которых выиграл борец нашей деревни, не больше, чем $20 \cdot 20 - 110 = 290$.
Ответ: 290.
