There are 100 boxers, each of them having different strengths, who participate in a tournament. Any of them fights each other only once. Several boxers form a plot. In one of their matches, they hide in their glove a horse shoe. If in a fight, only one of the boxers has a horse shoe hidden, he wins the fight; otherwise, the stronger boxer wins. It is known that there are three boxers who obtained (strictly) more wins than the strongest three boxers. What is the minimum number of plotters ? Proposed by N. Kalinin
Problem
Source: tuymaada 2006 - problem 5
Tags: combinatorics solved, combinatorics
17.07.2006 20:05
Let's assume we have $p$ plotters and $u$ usual boxers, ie boxers who are not the three strongest and who do not participate in the plot. If $p$ is minimum, the plotters should not use horseshoes on normal boxers, because it does not matter how many games they win. So we will assume that all plotters are stronger than usual boxers. In that case, the three strongest boxers and the plotters each get $u$ wins. Let boxer $s_{1}$ be the strongest boxer, $s_{2}$ the second strongest one, etc.(note that in that case the plotters are boxes $s_{i}$, $4\le i\le p+3$) Then boxer $s_{1}$ beat boxer $s_{2}$ and $s_{3}$ and got $2$ wins among the three strongets boxers; boxer $s_{2}$ got one win, boxer $s_{3}$ got $0$ wins. Among the $p$ boxers, boxer $s_{4}$ got $p-1$ wins, boxer $s_{5}$ got $p-2$ wins, boxer $s_{6}$ got $p-3$ wins. We want minimum $p$ so the boxers $s_{4},s_{5},s_{6}$ should be the ones getting more wins than boxers $s_{1},s_{2},s_{3}$. Each boxer $s_{4},s_{5},s_{6}$ should use a horseshoe on one of $s_{1},s_{2}, s_{3}$(to make $p$ a minimum) and so will get an extra win, therefore the total number of wins $s_{4}$ will get is $u+(p-1)+1$, $s_{5}$ will have $u+(p-2)+1$ wins, $s_{6}$ will obtain $u+(p-3)+1$ wins. To minimize the number of wins of $s_{1},s_{2},s_{3}$ each plotter should use a horseshoe on them. To minimmize te maximum number of wins that $s_{1},s_{2},s_{3}$ will get, we need $\frac{p}{3}+1$ plotters using horseshoe on $s_{1}$, $\frac{p}{3}$ plotters using horseshoe on $s_{2}$, $\frac{p}{3}-1$ plotters using horseshoe on $s_{3}$. Then the total number of wins each of $s_{1},s_{2},s_{3}$ will get is $u+1+\frac{2p}{3}$. Now, we need the minimum number of wins obtained by $s_{4},s_{5},s_{6}$ to be greater than maximum number of wins obtained by $s_{1},s_{2},s_{3}$, si have: $u+(p-3)+1>u+1+\frac{2p}{3}$ $\frac{p}{3}>3$. $p>9$. Taking $p=10$, we cannot reach the desired result:need at least $5$ plotters use horseshoe on $s_{1}$, at least $4$ to use horseshoe on $s_{2}$, at least $3$ to use horseshoe on $s_{3}$. Taking $p=11$, we cannot reach the desired result:need at least $5$ plotters use horseshoe on $s_{1}$, at least $4$ to use horseshoe on $s_{2}$, at least $3$ to use horseshoe on $s_{3}$. Finally, $p=12$ works: $5$ plotters use horseshoe on $s_{1}$, $4$ use horseshoe on $s_{2}$, $3$ use horseshoe on $s_{3}$. So, answer is $12$.