11
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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.

  1. $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.

  2. $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.

$\endgroup$
  • $\begingroup$ Is there a convenient way to indent various amounts? $\endgroup$ – Julian Rosen Jan 6 '16 at 1:47
  • 1
    $\begingroup$ Nice way to use information theory to scale the problem, @Julian Rosen. Too bad you had to give up on formatting. I have the same problem and have resorted to using <br> to force line breaks and using &emsp; and LaTeX tricks for indentation and vertical spacing but still hope that I've overlooked something. Very glad that what is available -- Markdown, MathJax and typewriter mode, though not all at the same time -- is very usable in general. $\endgroup$ – humn Jan 6 '16 at 3:32
  • 1
    $\begingroup$ I'm not sure I understand why at least 7 duesl are necessary. $\endgroup$ – Fimpellizieri Jan 6 '16 at 4:00
  • 3
    $\begingroup$ @Fimpellizieri Initially there are 120 possibilities. Each duel can rule out at most half those possibilities in the worst case. In order to reduce 120 down to 1 single possibility, you need to halve it seven times. $\endgroup$ – Mike Earnest Jan 6 '16 at 4:17
  • $\begingroup$ @MikeEarnest Hummm that makes sense! Thank you. $\endgroup$ – Fimpellizieri Jan 6 '16 at 4:47
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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:

  • Pick anyone. He fights with everyone undecided in his group to divide the group into two: one better than him and other worse than him.

In the worst case, it would be:

  • A fights with B,C,D,E (All belong to the better group with none in the other group: Group 1 {} Group 2 {B,C,D,E}) [Fights = 4]
  • B Fights with C,D,E (All belong to the better group with none in the other group: Group 1 {} Group 2 {C,D,E}) [Fights = 3]
  • C Fights with D,E (All belong to the better group with none in the other group: Group 1 {} Group 2 {D,E}) [Fights = 2]
  • D Fights with E (E wins: Group 1 {} Group 2 {E}) [Fights = 1]

Skill sequence: A < B < C < D < E

Total fight (Worst case) : 4 + 3 + 2 + 1 = 10.

In the best case, it would be

  • A fights with B,C,D,E (Groups equally split: Group 1 {B,C} Group 2 {D,E}) [Fights 4]
  • B Fights with C (B Wins: Group 1 {C} Group 2 {B}) [Fights 1]
  • D Fights with E (E wins: Group 1 {D} Group 2 {E}) [Fights 1]

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.

$\endgroup$
  • $\begingroup$ For $n$ fencers, the worst case can never need more than $\binom{n}{2}=\frac12 \cdot n (n-1)$ fights, since that's the number of pairs of fencers. $\endgroup$ – Fimpellizieri Jan 5 '16 at 15:44
  • $\begingroup$ Corrected the worst case calculation. $\endgroup$ – thepace Jan 6 '16 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.