# Riddler Express, June 29 2018

EDIT2: Even my second attempt was wrong. See the comments.

EDIT: I’ve got this wrong – see the bottom of the post.

This one is titled, “What Are The Odds World Cup Teams Play Each Other Twice?”. The question is simple:

Assuming we don’t know anything about the strengths of the teams in the tournament, what are the chances that any pair of teams in a 32-team World Cup plays each other

twice?

I’m pretty confident I’ve got this one, so here goes!

The chance of any two teams meeting each other is the product of a lot of *independent* events. These events being independent means that

What are the events? Or to put it another way, what needs to happen for the two teams to meet each other twice?

Firstly, to meet in the first round, they must be in the same group.

Then, to have any chance of meeting again, the two teams must finish first and second in the group.

Then, both teams must win their second round matches, and their quarter-final matches.

Lastly, both teams must achieve the *same* result in the semi-final match: either both must win their semi-finals, or both must lose. (If one team loses and the other wins, then one team will go to the final, and the other to the third-place play-off.)

If those are the things that need to happen, what are the chances of each of them happening?

Being in the same group: there are 32 spots in the World Cup, in eight groups of four. Whichever group the first team is in, there are then 31 spots left, and three of them are in the same group as the first team. So the chances of this are ^{3}⁄_{31}.

Finishing first and second in the group: this is related to the question, “how many ways can you choose two things out of a set of four different things?”, also called four choose two, or _{4}C_{2}. There are two related ways of thinking about this:

- Call the teams in the first round group A, B, C, and D. We want our pair of teams to win. We can say that A and B are the teams we care about, but it doesn’t matter which of the four letters we pick. How many different possible winning pairs are there? The pairs are easy to list: AB, AC, AD, BC, BD, CD. The teams A and B only appear together once in that list of six, so the chances of them coming first and second are
^{1}⁄_{6}. - Let’s say again, that the teams we care about are A and B. How many different possible results are there for the whole group? We can count them, starting with first place: there are four possibilities for the team in first, then there are three possible teams left that can come second, and two left that can come third. If we know the teams in first, second, and third place, then there’s no question about which team is fourth – it must be the team that is left. So the number of possibilities are 4 × 3 × 2 = 24. What are those combinations?

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA All 24 combinations are here, and you can see that the four combinations in which A and B are the top two teams have been underlined. Four possible results out of 24 =

^{1}⁄_{6}. That’s the same as the answer that we got through the first method, thankfully.

Both teams win their second round and quarter-final matches: this is a total of four matches which all need to be won. Since we don’t know the strength of any of the teams, we can say that each of our teams has a 50% chance of winning any match it is in. 50% is a probability of ^{1}⁄_{2}, so the chance of all four matches being won is ^{1}⁄_{2} × ^{1}⁄_{2} × ^{1}⁄_{2} × ^{1}⁄_{2} = (^{1}⁄_{2})^{4} = ^{1}⁄_{16}.

Both teams get the same result in their semi-finals: there are four possible results in the semi-finals (team A wins or loses, at the same time as team B independently wins or loses). Two of these four results are good enough: two out of four = ^{2}⁄_{4} = ^{1}⁄_{2}.

Putting it all together: the combined chance of all of these events happening is just the chance of each of them happening individually multiplied together:

^{3}⁄_{31} × ^{1}⁄_{6} × ^{1}⁄_{16} × ^{1}⁄_{2} = ^{1}⁄_{31} × ^{1}⁄_{2} × ^{1}⁄_{16} × ^{1}⁄_{2} = ^{1}⁄_{1984}

So, not very likely!

That’s the Riddler Express for this week. Riddler Classic is still stumping me.

Edit: a friend pointed out that I have misinterpreted the question:

…what are the chances that any pair of teams in a 32-team World Cup plays each other

twice?

I have considered “any pair” to mean “any given pair” – answering the question, “If you pick two qualified teams before the draw for first round groups even happens, what are the chances that your pair of teams will play each other twice?” But “any pair” means “any pair at all”, not “any pair you pick before the tournament starts.” So the question actually means, “After the end of the tournament, what is the chance that at least one pair of teams will have played each other twice?”

I think I can answer that as well:

At the end of the first round, there are 16 teams left in the competition; eight pairs, where each pair played each other in the first round, and the two teams came first and second in their group.

Each pair has eight teams in the top half of the bracket, and eight teams in the bottom half of the bracket. Regardless of what happens in the bottom half of the bracket, four teams go out in the top half of the bracket after the second round matches, and two more go out after the quarter-finals. Two teams are left in the top half of the bracket, after the semi-final: one in the final, and one in the play-off.

Now in the bottom half of the bracket, there are the other halves of all eight pairs. Only two of those eight still have a paired team in the top half of the bracket – for the other six, their paired team is already out.

So two teams in the bottom of the bracket have a chance to play again against a team they played in the first round. To do that, either of them would have to win their second round and quarter-final match (50% × 50% = 25% chance), and then get the *same* result in the semi-final that their paired team in the top half of the bracket did (another 50% chance, for a total of 50% * 25% = 12·5% = ^{1}⁄_{8} for each of the two teams).

What’s the chance that at least one of those two teams makes it to play their other pair in the final or play-off? The chance that a particular one of them makes it is ^{1}⁄_{8}, so the chance that a particular team *doesn’t* make it is ^{7}⁄_{8}. The chance that neither team makes it is ^{7}⁄_{8} × ^{7}⁄_{8} = (^{7}⁄_{8})^{2} = ^{49}⁄_{64}. So the chance that *at least one team plays another team twice* is 1 – ^{49}⁄_{64} = ^{15}⁄_{64}.

I think the first question is the intended one for the Riddler, and I think that your answer to the second question is wrong.

The reason your answer to the second question is wrong is that you’re assuming (in the last paragraph) that the chances that one of the teams plays their group mate is independent of the chances that the other team plays their group mate. This isn’t right (to see this, consider the situation where we know that all four semi-finalists are from the same group. In this case, there is a 50% chance that any group-mates meet, but it’s also the case that for each team, there’s a 50% chance that it meets its group-mate.

I think it’s a bit fiddly to work out the exact probability that all four semi finalists are from two groups, which is why I think that the intended question is probably the first one you answered, which is less fiddly.

(it’s roughly 1/64 less than your answer, but not exactly – maybe 1/56 less. Empirically, these are pretty close: https://github.com/johnfaben/riddler/tree/master/world_cup)

*all four semi finalists are from the same two groups

Hi John, sorry I just approved these, I hadn’t been expecting actual comments!

I was hoping to be vindicated when I read the answer, but sadly, no:

https://fivethirtyeight.com/features/how-fast-can-you-deliver-pbjs-how-many-meerkats-can-survive/

I was going to do a final edit where I went over what I did wrong, but you’ve pointed out the error here.

In the model I was using, I was considering only the tournament after the knockout stage, and only one half of the bracket. For any team in the bracket whose group-stage counterpart got through to the final or 3rd place playoff, I had the correct probability, 1/8, of playing them again.

The way I understood my error was this: the problem was that I thought the two were independent. But if one team in half of the bracket does play its counterpart, that makes it slightly easier for the other team also to play its counterpart. That’s because, if the first team plays its counterpart, then that fixes the result of the semifinal. So the chances for the second team become 1 / 4, instead of 1 / 8.

I think this week’s Riddler Express is easy, but perhaps I should be a little less confident this time!