|
|
 |
Условие
На берегу круглого острова Гдетотам расположено 20 деревень, в каждой живёт по 20 борцов. Был проведён турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня А считается сильнее деревни Б, если хотя бы k поединков между борцами из этих деревень заканчивается победой борца из деревни А. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь k? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)
Решение
Оценка. Покажем, что при k > 290 такая ситуация невозможна. Упорядочим в каждой деревне борцов по убыванию силы и выберем в каждой деревне десятого по силе борца. Покажем, что деревня, в которой живёт слабейший из выбранных борцов, не может быть сильнее следующей за ней. Обозначим выбранных борцов в нашей и следующей деревнях через A и B соответственно. Тогда в нашей деревне 11 борцов не сильнее, чем A, а в следующей – 10 борцов не слабее B. Все 110 поединков между этими борцами закончатся в пользу второй деревни, то есть поединков, в которых выиграли борцы из нашей деревни, не больше 20·20 – 110 = 290.
Пример. Пусть среди борцов есть 210 новичков и 190 мастеров (каждый новичок слабее любого мастера). Пронумеруем деревни против часовой стрелки. Поместим в первую деревню одного слабейшего новичка и 19 слабейших мастеров; во вторую – двух новичков, слабейших из оставшихся, и 18 мастеров, слабейших из оставшихся; в третью – трёх слабейших из оставшихся новичков и 17 мастеров, слабейших из оставшихся; ...; в последнюю деревню – 20 сильнейших новичков. Покажем, что i-я деревня сильнее (i–1)-й при i > 1. Действительно, в ней есть i новичков и 20 – i мастеров. Мастера i-й деревни победят всех в (i–1)-й, а новички победят новичков, и всего побед будет i(i – 1) + {20(20 – i) = i² – 21i + 400. Абсцисса вершины этой параболы равна 10,5, поэтому минимальное значение в целой точке достигается при i = 10, 11 и равно 290, то есть i-я деревня сильнее (i–1)-й при k ≤ 290. Кроме того, мастера первой деревни победят новичков 20-й, и всего побед будет 20·19 = 380 > 290, то есть все условия выполнены.
Ответ
290.
