Permutations with conditions

Question

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?

Especially Lime · Accepted Answer · 2017-12-07T11:10:44.923

4

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

edited Dec 07 '17 at 11:10

answered Dec 07 '17 at 11:09

Especially Lime

40,828

why exactly half? – vik1245 Dec 07 '17 at 11:10
1

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. – Especially Lime Dec 07 '17 at 11:12
Lovely! Thanks! – vik1245 Dec 07 '17 at 11:14

score 4 · Answer 2 · answered Dec 07 '17 at 11:19

Consider cases:

Hermione comes first. Then there are $3! = 6$ arrangements behind her.
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$.
Hermione comes third, Lavender must be fourth. There are $2$ possible arrangements for Ron and Fred.

Altogether $6 + 4 + 2 = 12$.

score 1 · Answer 3 · answered Dec 07 '17 at 15:43

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.

Permutations with conditions

3 Answers3