Bogogn i.i.

On the shore of the round island Gdetotam, there are 20 villages, each inhabited by 20 wrestlers. A tournament was held where each wrestler faced all wrestlers from all other villages. Village A is considered stronger than village B if at least $k$ matches between wrestlers from these villages end with a victory for a wrestler from village A. It turned out that each village is stronger than the next one in the clockwise direction. What is the maximum value that $k$ can have? (All wrestlers have different strengths, and the stronger wrestler always wins in a match.)

#
Evaluation. Let's show that when $k>290$, such a situation is impossible. We will order the wrestlers in each village by decreasing strength and select the tenth strongest wrestler in each village. We will show that the village where the weakest of the selected wrestlers lives cannot be stronger than the next one. Let's denote the selected wrestlers in our and the next village as $A$ and $B$ respectively. Then, in our village, there are 11 wrestlers who are not stronger than $A$, and in the next village, there are 10 wrestlers who are not weaker than $B$. All 110 matches between these wrestlers will end in favor of the second village, meaning the number of matches won by wrestlers from our village is no more than $20 \cdot 20-110=290$.

Example. Suppose among the wrestlers there are 210 novices and 190 masters (each novice is weaker than any master). Let's number the villages counterclockwise. Place the weakest novice and 19 weakest masters in the first village; in the second village, place the two weakest remaining novices and 18 weakest remaining masters; in the third village, place the three weakest remaining novices and 17 weakest remaining masters; ...; in the last village, place the 20 strongest novices. We will show that the $i$-th village is stronger than the $(i-1)$-th village when $i>1$.

Indeed, in it, there are $i$ novices and $20-i$ masters. The masters of the $i$-th village will defeat all in the $(i-1)$-th village, and the novices will defeat the novices, and the total number of victories will be $i(i-1)+\left\{20(20-i)=i^{2}-21 i+400\right\}$. The x-coordinate of the vertex of this parabola is 10.5, so the minimum value at an integer point is achieved at $i=10,11$ and is equal to 290, meaning the $i$-th village is stronger than the $(i-1)$-th village when $k \leq 290$. Moreover, the masters of the first village will defeat the novices of the 20th village, and the total number of victories will be $20 \cdot 19=380>290$, meaning all conditions are met.

## Answer

290.

Send a comment