(This post participes on the 111th edition of the Carnival de Mathematics, hosted by the blog Boole's Rings.)
FIRST HALF
There’s a great commotion few days before the start of the Football World Cup Brazil 2014. The organizing committee has decided to introduce an amendment at the last minute.
They want to add more countries to t he 32 nationsalready qualified for the final tournament. There’re many national teams that have been left out of the championship.
Given the huge stir generated by this World Championship, and the disappointment of many countries for failing to qualify, World Cup organizers have decided to increase the number of participants.
Given the huge stir generated by this World Championship, and the disappointment of many countries for failing to qualify, World Cup organizers have decided to increase the number of participants.
The competition system initially established for the 32 countries was as follows: a first stage based on a league format with 8 groups of 4 countries, the first 2 teams of which qualify for next round.
The 16 teams qualified will meet on 3 knockout stages till the final, where the winner will take the World Cup.
However, if they want to add more countries, and achieve a not over-extended championship, they must necessarily adopt a new competition format, discarding the initial leagues and performing a knockout format from the beginning.
Moreover, given the availability of the football stadiums and the logistical problems that may result from this modification, they have determined to bring the 64 matches originally listed with the old system down to 60 games.
The Local Organizing Committee has called a meeting with several experts from the Department of Applied Mathematics of the Ministry of Education.At this meeting, the Committee chairman exposes to the other attendees the couple of issues that arise:
- The first issue consists on to determine the maximum number of teams that can participate if a total of 60 matches are held. We want the highest number of countries to come, because, first, we will have more visits of tourists from the participating countries, and second, we will have more income from television rights of those who choose to watch it at home.
- The second one is to analyze how many different ways we can arrange the tournament with knockout matches.
- What do you mean exactly?
- I mean that the championship can be played in many ways. For example, we can establish that there are 8 seeded teams, and make the other countries compete until there're only 8 teams to meet them in round of 16. Thus, if we represent the matches to dispute as small green rectangular stadiums, and teams with a blueish soccer clothing, our competition diagram looks like this:
- Or we can choose only 4 seeded teams and the rest are eliminated until there're only 4 national teams to face them.
- Or we set just 1 seeded team (the host country, of course), and the rest are eliminated until there is only one to play the final with us. Anyway, all the variations you can think of.
- I understand. But... it won’t be possible... It's a lot of work... for so little time.
- I don’t want excuses. Come on, let's get to work, and we’ll meet here again tomorrow.
The head of the Applied Mathematics Department is very concerned about these questions. Can you help him?
SECOND HALF
The following day, the mathematical experts meet again the members of the Organizing Committee.
- We'll try to solve the first question. What do you think about it? What’s the maximum number of countries we can call if 60 matches are held?
- Well, I think the best will be to make a match plan, as in tennis tournaments. We’ll represent the final match with a small soccer field, and we’ll draw 2 lines from it, to the two teams that will play the match. We have 1 match.
- Now we replace the shirts representing the teams with 2 pitches symbolizing the 2 semifinal matches. From each of them we draw another 2 lines, with the teams who play the matches. And if we add these 2 new matches to the one of the final, we already have 3 matches in total.
- And we go on with the 4 quarter-final matches, the 8 round of 16 matches and the 16 round of 32 matches. We now have a total of 1+2+4+8+16 = 31 matches.
- We still need 29 more games to complete the 60 matches we want to be played in the championship. So we can’t hold all the 32 matches of round of 64, since we would have a total of 31 + 32 = 63 games. You can count the soccer pitches in the scheme, to check it.
- 3 matches are left over. So we remove 3 matches, and there’ll be 3 teams directly qualified for the round of 32.
- Now let's count the teams participating in the tournament: we must count all the shirts hanging like leaves at the ends of each branch.
- It's true, the diagram of the tournament looks like a tree. Well, after counting them, I get 61, that is, we can hold up to 61 countries, right?
- That's right, whenever the tournament is arranged with this competition scheme. But what about if we manage another distinct trees? If we want to have 8 top seeded teams, or if we want to have 4 seeded teams, always respecting the number of 60 games, the trees would be:
- What now? Will be there more or less countries this way? And what about if we think on other different trees?
- We can see that in these two examples we get also 61 countries, but I don't know what would happen to the rest of trees we can design...
- We can see that in these two examples we get also 61 countries, but I don't know what would happen to the rest of trees we can design...
- We’ll always get 61 countries, and we’ll use to a curious procedure to prove it.
- Let's think about the following: in all knockout games, there will always be a loser, that no longer will play more games. We just have to think that in 60 matches there will be 60 ‘losers’ countries, whom we have to add the final winner. Therefore, there will be 61 countries, regardless of the form the competition schedule takes.
-We can look at it in another way: if in every game we have represented a football pitch, we state that the team that wins the match and moves to the next phase occupies the darker half, while the loser is set in the lighter green part, we can see that there are 60 clearer parts corresponding to the 60 eliminated teams, to which it must be added the team that wins the tournament, who has always been on the dark area of its matches. So we have a total of 61 teams. And it doesn’t matter the 'tree' of the competition that we form.
- It's true. So we can say that the first question of finding the maximum number of countries is solved.
- Now let's study the second question: how many different ways we can arrange the tournament. In other words, we have to evaluate the distinct trees that we can design to organize the championship with 61 countries.
- Well, it doesn't seem very difficult. Let's start with a championship without teams. With zero participants, we could not organize any championship, right?
- Now consider a one-team championship. It's very easy. There’is only one way to do it: just give the trophy to the one team, and that's it.
- With 2 teams, both would play the final. There would only be one way to organize it.
- Correct.
- With 3 teams, there’s also only one possible way to arrange the event: first we bring together 2 teams, and then the winner plays with the third team, right?
- Indeed. But if instead of bringing together the first and the second team, we make the first and the third team face each other, or the second and the third, then we have two additional arrangements, right?
- No. It’s true that the teams would be different, but the pattern of competition would be the same: at first, 2 teams play a match, and the winner plays with the remaining team. For now, what we want is to find out how many distinct match schedules we can make and decide for one of them. Then we'll see how to put each of the national teams within that scheme, okay? So we’ll go on painting all teams with the same color.
- Perfect. Now we'll work with 4 teams. The most usual is to make them confront each other on 2 semifinals, and the winners play the final.
- But there’s another way to deal with them: eliminating one by one.
- So with 4 teams, we have 2 different trees. Let's see with 5 teams: there are 3 possible schemes.
- With 7 teams we can form 11 different trees. With 8 we build 23 trees, and with 9 we can design 46 trees. But it's increasingly difficult to draw the different options. I think this way we won't get anywhere...
- Maybe we should find a formula to calculate how many distinct trees can be formed with 61 competitors. To do this, we'll study the series we have so far, to see if we can deduce how it follows.
- It doesn’t seem that the numbers we’ve obtained obey any mathematical sequence. Maybe we should search on internet for a solution to our problem.
- Yes, but the first thing we have to do is to define exactly what we're looking for.
- Well, these trees we're drawing are called 'graphs' in mathematical terms. And as they have a hierarchical form, which simulates a tree (or a root), they’re also known by the name of ‘trees’ in Mathematics and Computer science.
- In addition, these trees are very special because from all of those little pitches (which we call nodes) representing the football matches, we start 2 lines (branches or children). There can’t be a game in which more than 2 teams meet, so we talk about ‘binary trees’. And no match can be played with only one team, so therefore, we say they’re 'strictly binary trees’.
- On the other hand, we said before that it doesn’t matter the order of the different branches, as we're looking at the structure of the tree, and it doesn't care who plays the matches. So we're talking about ‘strictly unordered binary trees’.
- We just have to use the internet browser, write 'how many strictly unordered binary trees can be formed', and wait for the results...
- Well, there aren’t many results. But I think none of them seems to fit what we're looking for. Perhaps we are not approaching the problem correctly.
- Maybe it's better to resume again the series of trees that we had previously calculated:
0 1 1 1 2 3 6 11 23 46 98
- And we introduce it on this very useful website, which recognizes all kinds of series from its terms:
- Aha! Here we've got the solution: it’s series number A001190, called the Wedderburn-Etherington series. We can see that within the utilities described on the web, there’s the one concerned with our problem: the number of distinct ways of organizing a single-elimination tournament for n players (with the players name left blank), that's it, the amount of possible different schedules that can be set for a number n of participants.
- Now we just have to click the link where T. D. Noe calculates a table with the first 200 terms of the series, and pick the result for 61 teams:
844206159208807054529
- What a number! Let's put the commas, for to have an accurate idea of its magnitude.
844,206,159,208,807,054,529
- Over 844 trillion different trees! Even in the Amazon rainforest there aren’t so many trees!
- It looks like a pretty big number. And we said we wanted to study all the cases to see which system we adopt, right? I think we’ll have to work 24 hours a day.
- Well, let's think a bit. If one of us devotes 1 minute to each 'tree', and he/she doesn’t eat , sleep, nor rest, he/she needs a total of 160,617,610,995,447 years to finish the work.
- We should put to work on it all the Department.
- Nah, even if all Brazilians (over 201 million people), worked in this task it would take 7,989,625 years to complete it.
- Well, nowadays that almost everyone likes football, how about we ask the help of the entire world population?
- In that case, it would take only 221,987 years to study for 1 minute each of the possible ways of organizing our 61-teams tournament.
- By the way, I assume you remember when I mentioned that we weren't interested in differentiating the various teams, and therefore we focused only on the structure of the championship.
- Yes, but I didn’t quite understand why.
- Let’s revisit the issue for one moment. We have 61 teams, so we want to know the number of different ways we can sort them. In Mathematics, we talk about the permutations that can occur in a set of 61 elements.
- That’s right. And it’s easy to calculate. Any of the 61 national teams can be the first one to be chosen. For each one of them, we will pick another team among the remaining 60 teams. For each of these combinations of 2 teams, we have 59 teams to choose the third country. And so on.
- Therefore, the total number of permutations of the 61 countries will be:
- By the way, I assume you remember when I mentioned that we weren't interested in differentiating the various teams, and therefore we focused only on the structure of the championship.
- Yes, but I didn’t quite understand why.
- Let’s revisit the issue for one moment. We have 61 teams, so we want to know the number of different ways we can sort them. In Mathematics, we talk about the permutations that can occur in a set of 61 elements.
- That’s right. And it’s easy to calculate. Any of the 61 national teams can be the first one to be chosen. For each one of them, we will pick another team among the remaining 60 teams. For each of these combinations of 2 teams, we have 59 teams to choose the third country. And so on.
- Therefore, the total number of permutations of the 61 countries will be:
61 · 60 · 59 · 58 · ..... · 3 · 2 ·1 = 61!
- Indeed, for brevity we use the expression 'factor of 61’, represented by the symbol of admiration. And if we calculate the product, we get the following result:
61! = 5.0758 · 10 83
- That’s a number five followed by 83 more figures. If you thought that the number of trees we saw before looked huge (8,4421 · 10 20), imagine how it will be this new number. And if we multiply the number of trees by the number of forms we can fit the 61 teams in them, we get a lovely number :
- Forty-two thousand eight hundred and fifty googols of different ways of organizing our championship! We must remember that a googol is greater than the number of hydrogen atoms in the known universe...
- Uff . Then, I think we’d better use the traditional method: 29 matches of round of 64, freeing three countries in this first round, and full direct eliminatory rounds since round of 32.
4.2850 · 10 104 = 42,850 · 10 100
- Forty-two thousand eight hundred and fifty googols of different ways of organizing our championship! We must remember that a googol is greater than the number of hydrogen atoms in the known universe...
- Uff . Then, I think we’d better use the traditional method: 29 matches of round of 64, freeing three countries in this first round, and full direct eliminatory rounds since round of 32.
- Brazil, and two others.
- Of course!
- Come on then! Let’s decide now which new countries we’re going to invite for completing the schedule of 61 teams. And we should think of organising something special for the opening ceremony: What about giving away some balls?
- Right. But first of all, if anyone is interested in this topic of tree structures, here you have some links to deepen on it: Tree (graph theory), Generation of Rooted Trees and Free Trees, Binary Tree.
- And here you have other links, if you liked the story and want to share it with your friends.
- Goodbye. And may the best win!
No comments :
Post a Comment