Final exan Problem 4.[10 points] In the final round of the World Cup, 16 teams play a single elimination tournament The teams are called A,B,C,.. P The tournament consists of a sequence of rounds In each round, the teams are paired up and play matches The losers are eliminated, and the winners advance to the next round The tournament ends when there is only one team left For example, three possible single-elimination tournaments are depicted below ABCDEFGH A BAC A D ACGE0 KCJDLBPIEF B E B E E B F P E P E E A L A H MNOP F Two tournaments are the same if the same matches are played and won by the same teams For example, the first and second tournaments shown above are the same, but the third is different. How many different tournaments are possible? Solution. Suppose that we draw the tournament so that the winning team in each game is listed above the losing team. Then the ordering of teams on the left completely determines all matches and winners. Therefore, there are 16! single-elimination tourn ments Another approach is to use a result from earlier in the course: the number of ways to pair up 2n people is(2n)! /n! 2. In a single-elimination tournament, we must pair up 16 teams, determine who wins the 8 matches between them, then pair up the 8 winning teams, detrmine who wins the 4 matches, and so forth. The number of ways in which this can be done is 4!24 2!22@@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� 5 C I L Final Exam Problem 4. [10 points] In the final round of the World Cup, 16 teams play a single￾elimination tournament. • The teams are called A, B, C, . . . , P. • The tournament consists of a sequence of rounds. – In each round, the teams are paired up and play matches. – The losers are eliminated, and the winners advance to the next round. – The tournament ends when there is only one team left. For example, three possible single­elimination tournaments are depicted below: B A E E D B E H C D B P E A H M K C J D L B P I E F O A H G M N A I A E M I A C G E O M K I B A C D G H F E P O N M L K J I A A I A E M I A C E G I K M O A B D E M F G H K J Two tournaments are the same if the same matches are played and won by the same teams. For example, the first and second tournaments shown above are the same, but the third is different. How many different tournaments are possible? Solution. Suppose that we draw the tournament so that the winning team in each game is listed above the losing team. Then the ordering of teams on the left completely determines all matches and winners. Therefore, there are 16! single­elimination tourna￾ments. Another approach is to use a result from earlier in the course: the number of ways to pair up 2n people is (2n)!/n! 2n. In a single­elimination tournament, we must pair up 16 teams, determine who wins the 8 matches between them, then pair up the 8 winning teams, detrmine who wins the 4 matches, and so forth. The number of ways in which this can be done is: 16! 8! 4! 2! 28 24 22 21 = 16! 8! 28 · · 4! 24 · · 2! 22 · · 1! 21 · N O P C C C C C C
C

C C
AA H  H A H  H A
A
AA A A A A

H  H C H  H HH  H  H HH 
H  H C C
C

C C
A A
AA H  H HH A  AA

H  H C C
C
C

C H  H H  H H  H HH 
H  H C A A
AA H  H HH  AA H  H H  H

H  H H  H H  H HH