There is an island and 20 houses at the beach around the island, each house with 20 wrestlers.

Question

There is an island and 20 houses at the beach around the island, each house with 20 wrestlers. Each wrestler fights with all wrestlers from other houses. There is no two wrestlers with the same power and the stronger wrestler always win. We say that house $A$ is stronger than house $B$ if there is $k$ fights in which fighters from house $A$ wins. What is a maximum $k$ if we know that each house is stronger than the neighboring house in the direction of the clock movement?

I was trying to solve this was but in the end I gave up and I read an official solution. I was very unsatisfied how it was solved, because they never say how they find this $k_{\max}$, just proved it is ok. Perhaps someone will have a different aproach here.

Here is an offical solution: http://natjecanja.math.hr/wp-content/uploads/2015/02/2012_izborno-rjesenja.pdf

Appeared:

• Serbia and Montenegro preparation test for IMO $2006$;
• III International Festival of Young Mathematicians Sozopol $2012$;
• Croatia TST for IMO $2015$;
• Swiss TST for IMO $2018$.

Answer 1

Too long for a comment.

I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.

The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers (from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank) from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20\cdot 20 – 10\cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.

An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark $210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, \dots, 20$, let's in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.

Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,\dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20\cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.