Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam In today’s article, I’d like to take a look at what a problem that arose in my maths class this week. What seems to be a simple matter of arranging teams quickly turns into a complicated counting problem involving several stages of thinking. First, I’d like to introduce two concepts that most of our readers are probably familiar with, but are crucial to understanding counting problems, so I will go over them for the benefit of those who may not have heard of them. Permutations are ways to arrange things which take into account the order they are in. For example, there are 6 ways to arrange the letters ABC: ABC, ACB, BAC, BCA, CAB and CBA. We can quantify the ways to permute n objects as n! which means in the above case we should have 3! = 6 ways to arrange the 3 letters, which checks out. Combinations are ways to arrange things when the order does not matter. If we wanted to choose 3 distinct ice cream flavours from 8 different possible flavours, we could do this in 8x7x6 ways, but we would then have to divide by 3! = 6 to account for the fact we overcounted by including different orderings (if we did not divide by 3!, we would have counted chocolate, vanilla, strawberry and vanilla, chocolate, strawberry as different choices, even though we do not care about ordering in this case). We now have the tools to tackle the problem from my maths class. Consider the problem of arranging 8 different football teams into 4 different quarter-finals. How many different ways can this be done? At first, this may seem like a simple question. If we consider the first quarter-final, there are (8x7)/2 = 28 ways to choose 2 teams from the 8. There are (6x5)/2 = 15 ways to choose 2 teams from the remaining 6, (4x3)/2 = 6 ways to choose 2 teams from the remaining 4, and (2x1)/2 = 1 ways to choose 2 teams from the last 2 (obviously). So, there are 28x15x6x1 = 2520 ways to arrange 8 teams into quarter-finals. However, this is not the only way to approach the problem. There are 8! = 40320 ways to arrange 8 teams in a list. For the purposes of this problem, it does not matter whether a pair of teams A and B are in positions 1 and 2, or if positions 1 and 2 are held by B and A respectively, because they would be playing each other regardless. This applies to the teams in positions 3 and 4, 5 and 6 as well as 7 and 8. This means there are 24 instances of overcounting, so we divide 40320 by 24 = 16 to get 2520, which is the same answer we arrived at above. Although it is satisfying to be able to arrive at the same answer through two different methods, the number we obtained is not strictly correct in terms of meaningfully different games. Consider the diagram below, which shows one half of the quarter-finals. Regardless of whether AB and CD are arranged AB, CD or CD, AB (with rearranging possible within the two pairs as well), the semi-final matchup will be the same - one team from the AB pair, and one team from the CD pair. This means our method above is overcounting, so now we need to figure out by how much we are overcounting so that we can account for the discrepancy.
Essentially, our first method failed to account for the fact that the draw A-B, C-D, E-F, G-H is indistinguishable from the draw A-B, G-H, C-D, E-F. There are 4! = 24 different ways to rearrange the 4 quarter-final pairings, so dividing 2520 from above by 24 gives us our final answer of 105 meaningfully different draws. Once again, we can arrive at this same answer through a different route. It is easier to first consider the simpler case of just 4 teams (semi-finals). If the 4 teams are A, B, C and D, you can pair A with either B, C or D (3 choices) and there is only one choice for the remaining pair, so there are 3 ways to arrange 4 teams. If there are 6 teams, you have 5 choices for who to pair A with, and then 3 choices to arrange the remaining 4 teams (as calculated in the isolated 4 team case), so there are a total of 5x3 = 15 ways to arrange the 6 teams. Moving on the 8 team case, the number of arrangements is then simply 7 times the number of arrangements for 6 teams, so our answer is 7x15 = 105. The objective of this article was to show how complex even deceptively simple problems can be, not to dissuade our readers, but to encourage careful critical thinking from the start of tackling a problem. We have also demonstrated how problems can be solved using multiple different, but equally valid, methods. Let us know in the comments what you would like to read about next!
3 Comments
Val
27/6/2020 12:26:59 pm
Can't believe you did me dirty like this my dude!
Reply
Val
27/6/2020 12:28:11 pm
Also, why is it not 8C4 *3^2 (giving 315?)
Reply
10/6/2023 04:22:15 am
I encourage you to read this text it is fun described ...
Reply
Leave a Reply. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|