There are five fencers. Each has a particular skill level, all of which are different. When two fencers duel, the one with the higher skill level always wins.
How many duels do the fencers need to hold in order to rank themselves from best to worst, in the worst case?
There are $5!=120$ possible orderings of the fencers, so we need $\log_2(120)\approx 6.9069$ bits of information. Each duel provides at most $1$ bit of information, so at least $7$ duels will be necessary. Here is a way to determine the ordering in $7$ duels.
Call the fencers $A$, $B$, $C$, $D$, and $E$.
First $A$ and $B$ duel, by symmetry we assume $A$ wins. Then $C$ and $D$ duel, we assume $C$ wins. Next $A$ and $C$ duel, we assume $A$ wins. Now we have $E$ and $C$ duel. Here we separate into cases.
$E$ beats $C$. We then have $B$ and $C$ duel.
a. $B$ beats $C$. There are three possible orderings: $A>B>E>C>D$, $A>E>B>C>D$, and $E>A>B>C>D$, and two more duels ($E$ vs $A$, then $E$ vs $B$) determine the ordering.
b. $C$ beats $B$. There are four possible orderings: $A>E>C>B>D$, $E>A>C>B>D$, $A>E>C>D>B$, and $E>A>C>D>B$, and two more duels ($A$ vs $E$, then $B$ vs $D$) determine the ordering.
$C$ beats $E$. We then have $E$ duel $D$.
a. $E$ beats $D$. We then have $B$ duel $E$.
(i): $B$ beats $E$. There are only two possible orderings: $A>B>C>E>D$ and $A>C>B>E>D$, and having $B$ and $C$ duel determines the ordering.
(ii): $E$ beats $B$. There are only two possible orderings: $A>C>E>B>D$ and $A>C>E>D>B$, and having $D$ and $B$ duel determines the ordering.
b. $D$ beats $E$. We then have $B$ and $D$ duel.
(i): $B$ beats $D$. There are only two possible orderings: $A>B>C>D>E$ and $A>C>B>D>E$, and having $B$ and $C$ duel determines the ordering.
(ii): $D$ beats $B$. There are only two possible orderings: $A>C>D>B>E$ and $A>C>D>E>B$, and having $B$ duel $E$ determines the ordering.
I think it should be
8 duels
Divide the five randomly into two groups - one of size 2 and the other of size 3.
Create ranks within the groups by making them fight each other. This takes 1 + 3 = 4 duels.
Let the group of two be A > B and the group of three such that C > D > E. We now need to insert A and B into the C,D,E group.
Make B fight E. If B wins, B should fight D and so on... The moment B loses, A should fight the winner and fight his way up the ranks.
In the worst case, B loses to E, and A must thus have to fight E, D and then C to determine his final rank. This takes another 4 duels.
I ended up with the same answer as @Manal, but a bit diferently.
For ordering two fencers you need one duel. Let's name it A>B (1 Duel)
For an extra fencer (3) you'll need 2 more duels in the worst case (First against either one, then against the other). Rename them A>B>C. (1+2 Duels)
For an extra fencer (4) you'll make him duel B, and then the A or C, depending whether hi won or lost. Rename them A>B>C>D. (1+2+2 Duels)
Finally, for the fifth fencer you'll make him duel B, and then, in the worst case, C and D. (1+2+2+3 Duels)
In the end it's 8 Duels (worst case)
Assuming Transitivity holds i.e if A > B and B > C then A > C, then solving this is like sorting an array of 5 elements.
Applying DivideAndConquer algorithm.
Let the fencers be A,B,C,D,E. Now lets follow the below steps:
In the worst case, it would be:
Skill sequence: A < B < C < D < E
Total fight (Worst case) : 4 + 3 + 2 + 1 = 10.
In the best case, it would be
Skill sequence: B > C > A > E > D
Total fight (Best case) : 4 + 1 + 1 = 6
In general, for 'x' fencers, in the worst case (x-1)*x/2 fights needs to be fought.
