2
$\begingroup$

I'm trying to solve a question involving permutations with conditions.

I was reading the following problem:

Five runners competed in a race: Fred, George, Hermione, Lavender, and Ron.
Fred beat George.
Hermione beat Lavender.
Lavender beat George.
Ron beat George.
Assuming there were no ties, how many possible finishing orders could there have been, given only this information?
A 1
B 6
C 12
D 18
E 24
F 120

From the information given, I figured out that George (G) came last.
So, the finishing order was betwen Fred (F), Hermione (H), Lavender (L) and Ron (R).

Now I know from this list that there are

$$4 \times 3 \times 2 \times 1 = 24$$ ways to arrange the final order. But I can't seem to convert the information

Hermione beat Lavender

to find the final answer. I'm stuck. How do I get to the final answer, which is C?

$\endgroup$
4
$\begingroup$

As you say, there are $24$ ways for George to finish last, and the valid permutations are simply those with George last and Hermione beating Lavender. Now exactly half of the permutations with George last have Hermione beating Lavender (group the permutations in pairs which differ by swapping H and L; each pair has one valid permutation and one invalid). So the answer is $24/2=12$.

$\endgroup$
  • $\begingroup$ why exactly half? $\endgroup$ – vik1245 Dec 7 '17 at 11:10
  • 1
    $\begingroup$ I've edited to clarify a bit. You can divide the permutations into pairs, one good and one bad. So RHFLG (good) is paired with RLFHG (bad), etc. $\endgroup$ – Especially Lime Dec 7 '17 at 11:12
  • $\begingroup$ Lovely! Thanks! $\endgroup$ – vik1245 Dec 7 '17 at 11:14
4
$\begingroup$

Consider cases:

  1. Hermione comes first. Then there are $3! = 6$ arrangements behind her.

  2. Hermione comes second. Lavender has $2$ possible places $3$rd and $4$th, the places left have $2$ possible arrangements of Ron and Fred, $2 \cdot 2 = 4$.

  3. Hermione comes third, Lavender must be fourth. There are $2$ possible arrangements for Ron and Fred.

Altogether $6 + 4 + 2 = 12$.

$\endgroup$
1
$\begingroup$

Just my two cents: I consider the following approach to be simplest:

We see that Hermione comes before Lavender and that comes before George. Fred and Ron come anywhere before George.

So we have sequence HLG. First, we must insert Fred anywhere before George. There are 3 possible positions for him (.H.L.G). Then, we must insert Ron anywhere before George. There will be Fred somewhere, so there are 4 possible positions for him (for instance, .H.F.L.G). Total number of permutations = 3 × 4 = 12.

$\endgroup$

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.