3. 20 different villages are located along the coast of a circular island. Each of these villages has 20 fighters, with all 400 fighters having different strengths.

Two neighboring villages $A$ and $B$ now have a competition in which each of the 20 fighters from village $A$ competes with each of the 20 fighters from village $B$. The stronger fighter wins. We say that village $A$ is stronger than village $B$ if a fighter from village $A$ wins at least $k$ of the 400 fights.

It turns out that each village is stronger than its neighboring village in a clockwise direction. Determine the maximum value of $k$ so that this can be the case.

Answer: The maximum value is $k=290$.

## Solution:
We first give a construction and then prove that more than 290 is not possible. O.B.d.A we can assume that the fighters have strengths 1 to 400, and we number the villages clockwise from one to twenty.

Construction: In the first village live the fighters of strength 400,190, 189, 188, . . In the second village live 399,398, 171,170,..,157, 156, and so on, in the last village live the fighters 210,209,...,192,191. To put it more clearly, we first distribute the fighters with strength greater than 190 to the villages, into the first village 400, into the second village 399, 398, into the third village 397, 396, 395, etc.. Then we fill the villages with fighters with a maximum strength of 190, into the first village 190,..,172, into the second village $171, \ldots, 156$, etc.

Note that village $x$ has just $x$ fighters with strength greater than 190 and $20-x$ fighters with strength less than 191. For $x \in\{1, \ldots, 19\}$ the fighters with strength greater than 190 win against all fighters of village $x+1$. The fighters with strength less than 191 win against the fighters with strength less than 191 in the next village, so they each win $(20-(x+1))$ times. In total, village $x$ wins $20 x+(20-x)(20-(x+1))$ times. The calculation shows that each of these villages wins at least 290 times. Now let's look at the twentieth village. Its fighters win against nineteen fighters from village one, so the twentieth village wins more than 290 times. Thus $k=290$ is possible.

Upper bound: Assume that $k>290$ goes. We call fighters with a maximum strength of 200 weak. There are 200 weak fighters and twenty villages, so there is at least one village that has at least 10 weak fighters. We count how many times this village can win. The remaining fighters in the village win a maximum of $10 \cdot 20=200$ times. This means that the 10 weak fighters must win at least 91 times. The next step is that at least one of the 10 weak fighters must win 10 times. Consequently, the following village also has at least 10 weak fighters. Using the same argument, we conclude in turn that each village has at least 10 weak fighters. It also follows from the argument that the strongest of the weak fighters must be stronger than the strongest of the weak fighters from the following village, otherwise he cannot win 10 times. However, since we can apply the argument in turn, it also follows that the strongest of the weak fighters in the first village must be stronger than himself, which is not possible. Contradiction, therefore $k \leq 290$.