Mathematica competitions in Croatia

We first show that $k>290$ is impossible. In every village we rank the fighters (from 1 to 20) according to their strength and we consider the tenth fighter in every village. Let the weakest of these considered fighters comes from the village $A$. Then in any other village $B$ (and in particular in the neighbour of $A$) at least 10 fighters (from the strongest to the tenth by strength) from $B$ has won against 11 fighters (from the tenth to the weakest) from $A$. Hence the number of fights in which the fighters from $A$ have won is at most $20\cdot 20-10\cdot 11=290$, a contradiction with the assumption that the village $A$ is stronger than its neighbour.

We construct an example showing that $k=290$ can be obtained. Let the 400 fighters be ranked by their strength (1 is the weakest, 400 the strongest), and consider them as 210 weaker fighters (from 1 to 210) and 190 stronger fighters (from 211 to 400). In the village $A_i$ we put $i$ of weaker and $20-i$ of stronger fighters, more precisely in $A_1$ the fighters ranked 1 and 211–229; in $A_2$ fighters ranked 2–3 and 230–247; etc.

We show that the village $A_i$ is stronger than the village $A_{i-1}$ for $i=2,\dots ,20$. All weaker fighters from $A_i$ have won against all weaker fighters from $A_{i-1}$, and all stronger fighters from $A_i$ have won against all fighters from $A_{i-1}$. Hence the number of fights in which a fighter from $A_i$ has won is $i\cdot (i-1)+(20-i)\cdot 20=i^2-21i+400$. This expression attains its minimum for $i=10$ or $i=11$ and then equals 290. In addition, the 19 stronger fighters from $A_1$ have won against all fighters from $A_{20}$, and since $20\cdot 19=380>290$, the village $A_1$ is stronger than the village $A_{20}$. This proves the assertion of the problem.