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.