Tuesday, 24 June 2014

The mathematical murderer

A player has been killed in the locker room at halftime of a match of the World Cup Brazil 2014. A series of mathematical clues lead you to solve the mystery, with the help of inspector Larry Flanagan and official Joe Vitruvius, that will introduce the fascinating world of Combinatorics. Do you dare to solve the case?

A player has been killed in the locker room at halftime of a match of the World Cup Brazil 2014. A series of mathematical clues leads you to solve the mystery, with the help of inspector Larry Flanagan and official Joe Vitruvius, that will introduce the fascinating world of Combinatorics.

Do you dare to solve the case?

(This post participes on the 112th edition of the Carnival de Mathematics, hosted by the blog Theorem of the Day.)

The mathematical murderer

Nobody could believe it. They were waiting for him to begin the second half of the match, but he didn’t go out to the pitch. Finally, the physical trainer went down to the changing room to see what was happening, and found him there, lying on the floor, with a dagger in his chest.

It was Drakulic, the center forward and captain of the national team of Transylvania, that had brilliantly qualified for the first time for a final tournament of a World Cup, that this year Brasil holds.

None of the players remembered who had been the last one to leave the locker room, because they were very upset by the talk of their coach, Pep Tourinho, as they were losing at halftime by 2 goals to 0 with the national team of Western Micronesia.

The organizers of the Championship wanted the case to be solved quickly and discreetly, so they requested the Police for their best officials, so as to solve the case as soon as possible.

In few minutes, inspector Larry Flanagan, and agent Joe Vitruvius, from the Mathematics Department of the Police, arrived to the stadium.

Why were they chosen? Well, Larry Flanagan (F) was the most brilliant inspector of the police. But he wasn’t very good at Mathematics.

The collaboration of an official of the Mathematics Department seemed essential because, stuck on the dagger, there were three scraps of the today’s newspaper, all of them related to the match they were going to play, and with some mathematical notations written in them.

Furthermore, the news clippings didn’t have the traditional rectangular shape, but they were cut in a triangular shape, and the dagger went through them by their center.

Everything made them think that the criminal was a person who liked Mathematics, and that, she/he had left some clues whose resolution will lead them to the assassin.

Therefore, Joe Vitruvius (V) contribution seemed fundamental to solve the case, because he was an expert in the resolution of such enigmas.

The inspector got into work. He took the scraps, and read the first one: ‘For tonight’s match, our national coach hesitates which pair of central defenders will pick among the 4 available players’. On the upper part of the scrap, there was a mysterious note in red: (4 2).

F: I don’t understand the relation between this news of the defenders and the murdered player, who is a forward. Moreover, what will these numbers in red mean, 4 and 2, written one below the other, and in brackets? –inspector Larry Flanagan said.

V: It could be a mathematical notation, a binomial coefficient, which represents the combinations of 2 elements taken from a set of 4 items. In this case, it can indicate the number of possible combinations of 2 central defenders that the coach can pick if he has 4 players available to play in this position. As we would say in our Department, combinations (without repetition) are the number of subsets of k distinct elements that we can extract from a set of n elements. – Joe Vitruvius answered.

F: I see. If we have 4 players, whom we’ll call A, B, C and D (Transylvanian names are really complicated, so we’ll better use these letters), the coach may choose the following pairs of players: AB, BC, CD, AC, BD, and AD. This is, a total of 6 different pairs, right?

V: Right. This will be that way if we don’t mind what position they play. That is, it doesn’t matter if each player plays on the right or on the left of the pitch. In other case, we’d have a total of 12 combinations, because we should count the same pairs, but changing their order: BA, CB, DC, CA, DB, and DA. This way, we’d talk about partial permutations (without repetition) of 2 elements taken from a set of 4 items, and not about ‘combinations’.

F: Well, it seems that the first clue leads us to number 6. Let’s see the next scrap: ‘Indignation in Brașov. After the good season of the Sporting of Brașov, the coach will only field 2 of the 7 players of the team, that he took with him to Brazil’. Also in this clipping somebody has written a 7 and a 2, in brackets and one above the other.

F: Don’t tell me, Joe. I think this time I’ve found it by myself: the notation (7 2) represents the number of possible combinations of 2 elements taken from a set of 7 players, that the coach can pick. This is, the number of possible different pairs of players from Sporting that the coach may choose to play the match. Am I wrong?

V: No, you aren’t, inspector Larry. I see that you learn very quickly.

F: Ok, let’s see the pairs we can get. If we have 7 players, whom we’ll call A, B, C, D, E, F and G, their combinations will be: AB, FE, AC, CD, AD, BD, CF...

F: Oops! I think I’ve lost. Now it’s no so easy to calculate them... I’m going to start again, in a more ordered way: AB, AC, AD, AE....

After a while, the inspector comes to the result:


F: I think we have 21 pairs, but I’m not absolutely sure that I haven’t forgotten any…

V: Yes, that’s right. Nevertheless, in this case, it would be better to use Mathematics. The formula for calculating the combinations of k elements taken from a group of n elements, is as follows:

F: Where does this formula come from?

V: Well, let’s think on the first player that the coach can choose. Clearly he has 7 possible candidates, the 7 players from Sporting. When he’s going to choose the second, he only has 6 players to pick, right? Therefore, for each of the 7 players that can be chosen initially, there will be 6 possible playmates. So we have 7 x 6 = 42 possible pairs:


V: But in this case we get again the partial permutations of 2 elements taken from a set of 7 elements, as we have repeated pairs: AB and BA, for instance. And we said that we don’t care the position in which they play. What could we do to remove them from our formula?

F: I can’t imagine how...

V: We should divide the result by the number of possible ways we can find the same combination of players, but in a different order. It’s what, in our Department, we call ‘permutations’ (without repetition): the number of distinct ordinations we can make in a set of elements, using all the numbers, but not repeating them.  

F: And how do we calculate the number of permutations?

V: It’s quite simple: If we have k elements, we have to think that any of them can be the first one. Then, there will be (k-1) elements that can be in second place (as we can’t repeat them). There will be (k-2) elements available for the third place. And so on. The total of different ways we can sort k elements will be

P(k) = k • (k-1) • (k-2) • … • 3 • 2 • 1

V: In our Department we don’t like wasting time when writing such long formulas, so we invented a secret key for this product: ‘factorial of k’, that we write: k! So we can reduce our formula:

P(k) = k!

V: For our case with sets of 2 players, we’ll have that k! = 2! = 2 • 1 = 2

V: So now we have the result for our problem. To obtain the number of combinations of 2 elements taken from a set of 7, we have to divide the number of variations of 2 elements taken from a set of 7 items by the permutations of 2 items:

F: That’s what I said at the beginning, without all these formulas!

V: It’s true, but you spent a lot of time to get the result. And there were only 7 players. What would happen if you have to choose, for example, 5 players from the 23 selected? Would you write all possible combinations?

F: Hummm… Ok. Continue your explanation, please.

V: Now, let’s modify slightly the precedent formula, by multiplying the numerator and the denominator by 5!

V: We’ve arrived to the initial formula, can you see it?

F: Correct. But I’m a little tired about all these figures, combinations, permutations, partial permutations… I think we’d better take the finger prints from the dagger, and we’ll solve the case more quickly.

V: Inspector, you know that assassins tend to wear gloves in these cases… Moreover, because of the celebration of the World Cup, the Laboratory is understaffed. And we know that they’re not so quickly in their analysis as we wanted.

F: All right. Let’s go on with our investigation. We take the third scrap: ‘Today everybody expects a hard fight in midfield, so the coach says he will choose 5 of the 7 midfield players he has brought for the World Cup.’ Above this news we can read another note (7 5).

F: Well, now we have a combination of 5 players taken from a total of 7, haven’t we? Let’s calculate it with the formula you have taught to me.

V: It’s also 21.

F: How did you calculate it so quickly?

V: I haven’t done any calculation, indeed. We have that

V: In general terms,

F: And why do we get the same result?

V: Well, you have to think that we can express in other terms the problem of calculating the number of possible combinations of 5 players if we have a total of 7 players. We can think about the 2 players that remain on the team bench each time the coach picks 5 players to enter the pitch. 


V: That way, for each group of 5 players selected to play we have a set of 2 players not selected. There will be as many distinct groups of 5 line-up players than groups of 2 players that stay on the bench.

V: So, instead of calculating how many groups of 5 starter players we can form, we can see how many groups of 2 reserve players we can get, if we have a total of 7 players, since the solutions will be the same. And as in the previous clipping we’ve already calculated that there were 21 possible combinations for this case, now we don’t need to calculate it again.

F: Perfect. Now we only have to fit the pieces we have. The results of the 3 mysterious parentheses (4 2),(7 2) and (7 5) turned out to be numbers 6, 21 and 21. I think that if the dagger went through the 3 scraps by their centre, maybe we should find the arithmetical ‘center’ of the obtained numbers, that is, their average:

F: Waw, 16! Just the number that the murdered player wears on his back!  

F: It seems that the murderer is a fan of Mathematics and of logic problems, and he’s going to make it difficult to us. And now, Joe, what can we do?

V: There’s a data that we haven’t used yet in our investigation, perhaps the most obvious: the scraps have a triangular shape.

V: If the murderer is a fond of Mathematics, and also if all the problems on the scraps are related to the discipline of Combinatorics, no doubt all leads us to the Pascal’s triangle. Do you know this triangle, Flanagan?

F: No, I don’t know what it is.

V: That’s normal. This triangle, as the cleverest criminals, adopts a lot of distinct personalities. For example, it’s also known as Tartaglia’s triangle. Anyway, and returning to our case, I’ll tell you that it’s a triangle very easy to draw up. First we write an 1 in the superior vertex, and then, above it, successively and in diagonal, we write the result of adding the 2 numbers above it. If there’s no number, we add a zero.

V: Now, we’re going to point, in this Pascal triangle, the results obtained. Look, inspector. In the first case (4 2), we take the fifth row (we leave out the first lonely 1) and we go to the third number, so we obtain the value 6. The same result as we get with our formula.

F: Why have you pointed put the third number on the fifth row, and not the second number on the fourth row?

V: Because the apex of the triangle corresponds to binomial coefficient (0 0). And, on each row n, the first number represents the combination (n 0). Thus, on our fifth line (4 0) is equal to 1, (4 1) is equal to 4, (4 2) is equal to 6, and so on. Agreed?

F: Yes. I didn’t think on number 0.

V: Now we’re going to do the same with (7 2) and (7 5). You can check that the 3 numbers make an awesome triangle, with a similar shape as the news clippings.

F: And as the triangle is symmetrical, now I understand why (7 2) is equal to (7 5).

V: Fabulous. Now, we only have to point out the number which is located at the geometrical center of the triangle we have drawn, because the dagger crossed the papers through their center. And we get number 20.

F: Which player has this number? Go and arrest him! – Inspector Larry Flanagan cried.

It was Vladimiric. The police didn’t take much time to catch him inside the stadium, and brought him to the locker room.

There, Vladimiric confessed his crime. He was Drakulic’s best friend since childhood. Drakulic had overcome him in every aspect of life: he had better academical records, was luckier with girls, had more friends and played football better. In fact, Drakulic was the captain of the national team of Transylvania, and Vladimiric was a reserve player, he played only a few minutes per match. But none of these things had been the cause that has lead to the fatal destiny.

F: And then, why have you done it? - Larry Flanagan asked him.

Well, Vladimiric said, there was only a pair of things in which Drakulic had never surpassed me: Mathematics and Logic problems. At least until today... When we were coming on the bus from the team hotel to the stadium, we made a bet on who was going to solve sooner the sudoku on the newspaper. And for the first time in our lives, Drakulic has been faster than me. I couldn’t bear it...

Si te gustó esta historia, puedes votar por ella en menéame y divoblogger. Muchas gracias.

Monday, 9 June 2014

Trees and googols at World Cup 2014

A new mathematical cocktail whose stars are the World Cup in Brazil, the different systems of competition, the number of Wedderburn-Etherington and tree topology.
(This post participes on the 111th edition of the Carnival de Mathematics, hosted by the blog Boole's Rings.)


The World Cup Brazil 2014 in MatifutbolThere’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.

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.

Match plan 2014 World Championship

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.

Group of Math expertsThe 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 Organizing Committee and mathematical experts discussing how to organize the World Cup

- 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: 

Scheme with 8 seeded teams

- Or we can choose only 4 seeded teams and the rest are eliminated until there're only 4 national teams to face them.

Scheme with 4 seeded teams

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

Scheme with one only seeded team

- 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?


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.

Scheme of a championshipo with 2 teams

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

Scheme of a championship with 4 teams and 2 semifinals

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

Scheme of a championship with 32 teams and a direct elimination system

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

Scheme of a championship of 64 teams and a direct elimination system

- 3 matches are left over. So we remove 3 matches, and there’ll be 3 teams directly qualified for the round of 32.

Uncomplete round of 64, with 3 teams directly qualified for next round

- 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:

Competition scheme with 61 countries and 8 seeded teams

Competition scheme with 61 countries and 4 seeded teams

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

Competition scheme with 60 teams

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

Championship with one team

- With 2 teams, both would play the final. There would only be one way to organize it.

- Correct.

Championshipo with 2 teams

- 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?

Championship scheme with 3 teams

- 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?

Two different ways of organising a championshipo with 3 teams

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

Competition scheme with 4 teams and 2 semifinals

- But there’s another way to deal with them: eliminating one by one.

Competition scheme with 4 teams and no semifinals

- So with 4 teams, we have 2 different trees. Let's see with 5 teams: there are 3 possible schemes.

Possible competition scheme for a tournament with 5 teamsPossible competition scheme for a tournament with 5 teamsPossible competition scheme for a tournament with 5 teams

- And with 6 teams, I can think of 6 possible ways.

Possible competition scheme for a tournament with 6 teamsPossible competition scheme for a tournament with 6 teamsPossible competition scheme for a tournament with 6 teams

Possible competition scheme for a tournament with 6 teamsPossible competition scheme for a tournament with 6 teamsPossible competition scheme for a tournament with 6 teams

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

Possible different competition models, regarding on the number of participants

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

Trees on Wikipedia- 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...

The mathematical experts and the Organising Committee are going to search on internet a solution for the problem

- 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:

OEIS. The On-Line Encyclopedia of Integer Sequences

First 200 terms ot the series A001190 of Wedderburn-Etherington- 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:


- What a number! Let's put the commas, for to have an accurate idea of its magnitude.


- Over 844 trillion different trees! Even in the Amazon rainforest there aren’t so many trees!

Approximately Brazilian population in 2013- 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?

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.

Two different ways of organising a 3-teams 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 :

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

Microwave background radiation of the 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 TreesBinary 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!

Si te gustó esta historia, puedes votar por ella en menéame y divoblogger. Muchas gracias. Si te gustó esta historia, puedes votar por ella en menéame y divoblogger. Muchas gracias.