6
$\begingroup$

Four English teams have progressed to the Champion's League quarter finals this year (for the first time since 2008). What is the probability that at least one quarter final will be an all-English tie?

My attempt

Obviously this is the complement of there being no all-English ties. Suppose the order of the teams (and the fixtures) matters (i.e. $AB,\;CD,\;EF,\;GH$ is a different draw from $DC,\;AB,\;HG,\;EF$). Then there are $8!$ total possible draws.

If we try to count the number of possible draws with no all-English ties, we have

  • $8$ choices for the first team and $4$ for the second;
  • $6$ choices for the third team and $3$ for the fourth;
  • $4$ choices for the fifth team and $2$ for the sixth;
  • $2$ choices for the seventh team and $1$ for the eighth.

This makes $8\times4\times6\times3\times4\times2\times2\times1=9216$ draws with no all-English ties, so the probability of at least one all-English tie is \begin{equation} 1-\frac{9216}{8!}=\frac{27}{35}. \end{equation}

Two questions:

  • Have I got the right answer?
  • What would be a more elegant way of going about this? Even if it is correct, I think my argument is 'lucky' in the sense that it wouldn't work for any other number of English teams.
$\endgroup$
4
$\begingroup$

For a generalisation, suppose we have $2n$ teams being drawn into $n$ distinct fixtures, $k$ of the teams being English. To prevent an all-English matchup we must have $k\le n$ by the pigeonhole principle, then out of $(2n)!$ possible draws the number with no all-English matchups is the product of

  • $\binom nk$ ways to choose which fixtures contain English teams
  • $k!$ ways to assign the English teams once their fixtures have been chosen
  • $2^k$ ways to decide for each English team whether they play at home first
  • $(2n-k)!$ ways to place the remaining (non-English) teams

Hence the probability there is at one all-English matchup is $$1-\frac{2^k\binom nkk!(2n-k)!}{(2n)!}=1-2^k\cdot\frac{\binom nk}{\binom{2n}k}$$ For the Champions League situation of $n=k=4$, the probability works out to $1-16\cdot\frac1{70}=\frac{27}{35}$, in agreement with your result.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As well as that, I'm a Liverpool fan... $\endgroup$ – Parcly Taxel Mar 13 '19 at 23:28
1
$\begingroup$

Surely it is 1 minus the possibility of no all English ties? It's drawing black & white balls out of a bag. I draw one, then 4 of the remaining 7 are a different colour. Next time I draw one from 6; 3 of the remaining 5 are different; third draw it's 2 from 3, and then I'm left with another mismatched pair. So the odds of this are 4/7 x 3/5 x 2/3 = 24/105 = 22.9% Odds of an all English tie are therefore 77.1%

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I come up with these probabilities after some calculations:

P(no all-English ties) = 8/35

P(one all-English tie) = 24/35

P(two all-English ties) = 3/35

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

First, let's consider the number of possibile English vs. non-English draws. We put the 4 English teams into the bag $X$, with 4 other teams in the bag $Y$. The number of draws is simply the number of bijections from $X$ to $Y$,

$n_0 = 4! = 24$

(This is precisely like combining 8 group winners with 8 group runners-up in the 1/16 CL draw, which yields $8!$ possibilities without any other constraints, such as no same-country no same-group clashes allowed).

Next, we have to find a total number of possible draws for $2 n = 8$ teams.

  • Way 1

    • We put 4 teams into one bag and the remaining 4 teams in another bag, in one of $\displaystyle k = {8 \choose 4}$ ways.
    • We connect teams from both bags as we did in the very beginning, in $m = 4!$ possible ways.
    • The problem is that each pair contributes twice, but the order within a pair should be irrelevant [$(12) \equiv (21)$], and there are $4$ pairs, so we've overshot $l = 2^4$ times.
    • Finally, the total number of draws is $\displaystyle N = \frac{k}{l m} = \displaystyle \frac{8!}{2^4 4!} = 105$.
  • Way 2

    • We start with $k = (2 n)! = 8!$ permutations of $2 n = 8$ teams from the $\{1, 2, 3, 4, 5, 6, 7, 8\}$ set.
    • Each permutation is actually composed of $n = 4$ pairs, each pair, e.g. $(12)$, corresponding to a game.
    • The order inside pairs is irrelevant, e.g. $(12)\ldots \equiv (21)\ldots$. Each pair contributes a factor of $2! = 2$ to the permuations number, so we've already overshot $l = 2^n = 2^4$ times.
    • Pair permutations don't change the draw either, e.g. $(12)(34)\ldots \equiv (34)(12)\ldots$, so we've additionally overshot $\displaystyle m = n! = 4!$ times.
    • Finally, the total number of draws is $N = \displaystyle \frac{k}{l m} = \frac{8!}{2^4 4!} = 105$.

Next, let's check our general expression for the total number of draws,

$N(n) = \displaystyle \frac{(2 n)!}{2^n n!}$,

for two simple cases:

  • $n = 1$ (final draw from $\{1, 2\}$ team set), possible permutations: $(12)$, $N(1) = 1$, looks good.
  • $n = 2$ (semi-final draw from $\{1, 2, 3, 4\}$ team set), possible permutations: $(12)(34)$, $(13)(24)$, and $(14)(23)$, $N(2) = 3$, looks good too.

$N(n)$ grows fast with n:

| n | N(n)
----------
| 1 | 1
| 2 | 3
| 4 | 105
| 8 | 2027025

Finally, back to the main question:

  • the probability of no English-English clash after the draw is thus $\displaystyle p_2 = \frac{n_0}{N(4)} = \frac{8}{35} \approx 0.23$.
  • the probability of at least one English-English game is $\displaystyle p_1 = 1 - p_2 = \frac{27}{35} \approx 0.77$.

In Parcly Taxel's answear the number of all draws, given as $(2 n)!$, is actually overshot, but the overshooting cancels out in the division (being a man of low reputation, I can't comment it below the answer).

I hope this is correct, and I hope Ajax wins this year's CL.

| cite | improve this answer | |
$\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.