Who will be Champion?

I stumbled on this puzzle on Facebook the day of the World Cup finals. How timely!

Puzzle. Sixteen teams play a single-elimination tournament, where the losing team is immediately out. The teams have different rankings, and a higher-ranking team always wins against a lower-ranking team. The initial seeding is random.
In the semifinals, A won against B, and C won against D. Given that B is stronger than D, what is the probability that A will become the champion?

Share:Facebooktwitterredditpinterestlinkedinmail

8 Comments

  1. Christian Miller:

    Alright, we know either A or C must be the best team (where teams are ranked 1 -> 16 from best to worst), so really this question is asking P(A = 1 | B > D … and all the other conditions)
    where P(A = 1 | B > D) + P(C = 1 | B > D) = 1.

    First, let’s be letter agnostic. For the 4 semifinalists, we know each will fit into one of the following ranges:
    – Finalist 1: 1
    – Finalist 2: 2 through 5 (5 occurs when 1 through 4 are all in one bracket quarter together)
    – Finalist 3: 3 through 9 (same reasoning as finalist 2)
    – Finalist 4: 4 through 13.

    Bringing letters into it, we can further state that:
    D must be in the finalist 4 group, since it must be worse than all other finalists (worse than A indirectly through transitivity).
    B must be either in the finalist 2 or 3 group, since it must be better than D but worse than A.
    C must be in one of the finalist 1,2, or 3 groups, since its only condition is that it is better than D.
    A must be in either the finalist 1 or 2 groups, since it must be better than both D and B.
    This means that A is between 1 and 5, and if it is not 1, C must be 1.

    So if A is 1, A > C, but is A is 2,3,4,5, C > A.

    P(A in (1,2,3,4,5) | B > D) = P(A = 1 | B > D) + P(A in (2,3,4,5) | B > D)
    P(A in (2,3,4,5) | B > D) = P(A = 2 | B > D) + P(A = 3 | B > D) + P(A = 4 | B > D) + P(A = 5 | B > D)

    We can translate slightly to make easier to calculate!
    P(A = 1 | B > D) = P(1 in A “cluster”) = 4/16
    P(A = 2 | B > D) = P(2 in A “cluster” & 1 in C “cluster”) = 4/16 * 4/15
    P(A = 3 | B > D) = P(3 in A “cluster” & (1,2) in C “cluster”) = 4/16 * 4/15 * 3/14
    P(A = 4 | B > D) = P(4 in A “cluster” & (1,2,3) in C “cluster”) = 4/16 * 4/15 * 3/14 * 2/13
    P(A = 5 | B > D) = P(5 in A “cluster” & (1,2,3,4) in C “cluster”) = 4/16 * 4/15 * 3/14 * 2/13 * 1/12

    Now for our final answer we take P(A = 1 | B > D) / P(A in (1,2,3,4,5) | B > D)
    First, we can multiply all terms by 16/4
    So we now have (conditionality assumed): P(A = 1) / [P(A = 1) + P(A in (2,3,4,5))] = 1/(1 + 1/3) = 3/4 or 75%.

  2. Lazar Ilic:

    The above comment is Wrong and also much more complex than is necessary for the task at hand. In particular there are say 4! = 24 permutations of the 16 teams which map together and hold those same ordered 4-tuples together. So the task is isomorphic with a reduction immediately ab initio into the case where there are in fact merely 4 initial teams relatively ordered. At which point [A,B,C,D] can be [1,2,3,4], [1,3,2,4], [2,3,1,4] so 2/3 should be the final answer.

  3. Bruce Fleischer:

    I also came up with 2/3, and agree with Lazar’s reasoning. I think one flaw in the logic in the first post is the hidden assumption that since finalist 4 (for example) has a rank between 4 and 13 overall, it has an equal probability of any of those. Being finalist 4 implies an overall rank between 4 and 13, but also includes the condition of being better than the three other teams in its bracket.
    It’s better to start at the semifinal stage. At that point we have no info about their relative ranks, so the 24 orderings of A,B,C,D are equally likely. Adding conditions A>B>D and C>D rules out all but 3 cases, leaving A>C with probability 2/3.

    Since the Monty Hall problem also has a probability 2/3 (that switching choices is better), I wonder if there’s a way to map this problem to Monty Hall that would let reasoning from one illuminate the other.

  4. Gennardo:

    The probability that the best team of the semifinal is paired against the worst team of the semifinal is 1/3. This is then only case in which the winner of the final would have had a worse team in the semifinal than the loser of the final. So the probability is 2/3.

  5. Jonathan Kariv:

    There is some ordering on A,B,C,D. We are given A>B>D and C>D. So D is the weakest and we only need to decide where C slots in compared to A and B.

    This leads to the three possible cases:
    A>B>C>D
    A>C>B>D
    C>A>B>D

    A wins with probability 2/3 and C with probability 1/3

  6. witzar:

    Let’s call players who reach semis 1,2,3,4 in order of their strength. Player 1 (the strongest) gets to play each of the remaining three with equal probability: 1/3.
    The condition specified in the problem is met if 1 gets to play 2 or 3, and not met if 1 gets to play 4. Therefore 2/3 is the answer.

  7. Kai:

    More interesting if it is asked to calculate the mathematical expectation of the rank of team A.

  8. lvps1000vm:

    So I decided to tally what happened in actual men’s Fifa World Cups.

    The champion beat the winner of the 3rd place playoff in the semifinal: 15 times
    1938 1954 1958 1962 1966 1974 (1978) 1982 1994 1998 2002 2006 2010 2018 2022

    The champion beat the loser of the 3rd place playoff: 5 times
    1934 1970 1986 1990 2014

Leave a comment