Let's now count the number of games in the tournament, more precisely, the setting is the following; We have five sport teams and they play the tournament meaning that each team played with each other. So the question is what was the number of games in this tournament? So visually it looks as follows. There are five teams A B C D and E and every two of them are connected by segment, meaning that they played the game. Basically our goal is just to compute the number of segments. This is essentially a toy problem, but what we're going to do is to design a general formula not for five teams but for any number of teams. Okay, so let's start to count. What we know is that there are five teams, so if we select any of them then we know that each team played exactly four games, right? Why is that? Well just because if the team is fixed, then there are four teams remaining and we know that this team played with every of these four teams, right? Which means that by the product through, what we know is that there are five teams and each of them played four games which gives us 20 games. But there is actually a flaw in this argument, so let's try to catch it and let's try to fix it. Okay so first of all, let's decrease the number of teams. So imagine if we had just three teams, so what would happen? Our argument actually gives that there are 6 games. Why is that? Well there are three teams and each of them played two games with each of the remaining two teams, so the number of games is six. But this is not correct, of course which can be just easily seen by considering this simple pitch. So we have three teams. There is a segment between any of them and the number of segments is three instead of six, right? To understand where is the flaw, let's just do all possible games. Okay so we have five teams: A B C D and E. So in the first row, we have all the games played by the team A. So we played with AB, with AC, with AD and AE. Makes sense, right? So for the second row lists all the games played by the team B. We played with A, with C, with D and with E, so still for some reason gives us 20 games in total. To understand what went wrong, let's try to rearrange all these games as follows. So we still have two rows and columns so there are still 20 games. At the same time, in this table you can easily see that each game is actually counted twice. So we see that we counted the game between the teams A and B as AB and BA, and this happened actually with every game. For example the game between B and C was counted as BC and CB. So this was our overestimation, so each game was counted exactly twice which means that we actually need to divide our resulting count by two which finally gives us a correct result; it is ten. Okay, so there is an important message for us. When we count something, we need to make sure that each object was counted exactly once, but if it turned out as in our example that we for some reason counted each object exactly K times, then it is easy to get the correct result. What we need to do is just to divide by K. So in our case we counted each game two times so what was needed to be done is to divide everything by two. Okay now let's generalize it to between the number of teams. The theorem here on the slide states that if we have N teams, then the number of games in a tournament where each game plays with each other exactly once is equal to N times N minus 1 divided by two. Okay let us prove it. So there are N teams, each of them plays exactly N minus one games because there are exactly N minus 1 teams remaining. Okay so the total number of games is N times N minus 1, but at the same time each game is counted twice because if a game involves teams I and J, then it was counted twice. First one we fix the team I and then it was playing with the team J and on the other hand and it was also counted when we fixed team J, with team J and then we counted the game as JI. Okay so we need to compute the product of N and then minus 1 and then divide it by two. This is the resulting number. Okay let's also compliment this with a recursive proof of the same formula. Okay so for this, let's denote by T of N the number of games in a tournament with N teams. Okay, then to get a reference relation for T of N, let's do the following; let's split all the games into two parts. On one hand we have all teams involving the first team. Okay so there are exactly N minus 1 side games. Why is that? Well because the first team played exactly N minus 1 games, we know this already. On the other hand we have all the remaining games. That is all the games that do not involve the first team. But this is the same as just all the games played by all the remaining teams. But this is not analysis T of N minus 1, right? So just by definition, we need to count all the games played by the teams two, three and so on N. So there are N minus one such teams. So we know that by definition T of N minus 1 is exactly this number. It's exactly the number of games played by N minus 1 teams. This gives us the following reference relations, T of N is equal to N minus 1 plus T of N minus 1. So now we need to somehow get a formula for T of N from this reference relation. Okay and for this we're going to apply the method, the so-called method of unwinding. Namely, let's just try our formula. T of N is equal to N minus 1 plus T of N minus 1, but then we can apply the same formula for T of N minus 1. So we leave N minus 1 but for T of N minus 1 we rewrite it as N minus 2 plus T of N minus 2. So we apply the same formula which give us N minus 2 plus T of N minus 2. Okay, but then we do the same with T of N minus 2. Okay this gives us N minus 3 plus T of N minus 3, and so on so we keep repeating this until we reach T of 1 or T of 0 which is in any case equal to zero. Right? Because if we had zero teams or if we had one team then the number of games is in any case equal to 0. What remains is N minus 1 plus N minus 2 plus and so on plus 2 plus 1 plus 0. This is the so called arithmetic series. Okay let me remind you how to compute the sum of such series. A simple but useful trick to remember here is the following: If you write all the terms in your arithmetic series and then you write this series once again but in the reverse order, then what is convenient is that in every column, the sum is going to be the same, and it is going to equal just N. Which means that it is very easy to compute the sum of all the numbers shown here on the slide. So we have N minus one columns, right? And in each column, the sum is equal to N which means that the sum of all these numbers is equal to N times N minus 1. At the same time to get the sum for arithmetic series, we need to remember that we counted it twice here, right? So this is our original series, and this is the reverse original series. So the sum in this [inaudible]. The same of course, which finally means that for the arithmetic series, the sum is equal to N times N minus 1 divided by 2. And this also is the answer for T of N. So this is another proof of the same formula. The number of games in the tournament is equal to N times N minus 1 divided by 2. Okay so finally let me compliment as usual with a simple script in Python. So for this, what we are going to do here is to take 8 teams. A B C D E F G H, so there are 8 teams, and we are going to use in the combinations method, we're going to generate all possible games between these 8 teams. So what we expect to get is N is equal to 8 in this case. So the formula gives us 8 times 7 divided by 2 which is just seven by four which is nothing else as 28. So let's run this script and indeed it produces all possible 28 such games. So the lengths of each list here is 4 and they were 4 lists. Okay, okay and finally let's do the formula, let's also show that our recurring formula also produces exactly the same result namely this was as you remember when T of N was defined to be the number of games in a tournament with N teams, and we proved that it satisfies the following formula. It is equal to N minus 1 plus T of N minus 1. And this allows us to just implement the following recursive procedure with the following base case. When N is at most 1, we just return 0 immediately. So if we then implement this procedure and task it to compute T of 8, then the output is going to be as expected, 28 which justifies our previous formula.
