2 Boredom and single-elimination tournaments revisited In this question, we revisit a problem you will undoubtedly remember from the midterm. A single- elimination tournament is one where players are paired up, and the winner of each game advances to the next round while the loser is eliminated. The n players are assigned slots numbered from 1 to n. In the first round, the player in slot 1 plays the player in slot 2, the player in slot 3 plays the player in slot 4, etc. The winner of the players in slots 1 and 2 will be assigned slot 1 for the next round, the winner of the players in slots 3 and 4 will be assigned slot 2 for the next round, etc. This is illustrated below: the players are named A through H, and the subscript represents the slot number for each round of the competition. A . D ES F G H round 1 round 2 B C E H. round 3 . H The organizers of the World Only-Relate championship want to make their tournament as exciting as possible and so are looking for a way to pair the contestants up to minimize the total boredom of the games of the tournament. They decide to calculate "boredom" as follows: They give each of players P1, P2, ... Pn a ranking r(Pi) that denotes how good player p; is: r(Pi) >r(pj) if player Pi is better than player Pj. Every time a player pi plays against a player Pj, the game generates a boredom equal to the difference between the players' rankings: Ir(Pi) - r(;). The total boredom is the sum of the boredoms of the individual games. On the midterm you assumed that n is a power of 2, and designed a greedy algorithm that takes in a list of n players with their rankings, and assigns a slot to each player so as minimize the sum of the boredom of the games of the tournament's schedule, assuming that whenever two players play each other, the best of the two always wins. The solution we gave can be summarized as follows: Sort the players by ranking increasing or decreasing) and assign slots based on the players' positions on the sorted list. That is, the worst player gets slot 1, the 2nd worst player gets slot 2, etc. To simplify the notation, we assume without loss of generality that r(Pl) > r(P2) > ... >r(Pn). A tournament schedule is a list of the games for the tournament, and it will be called canonical if All games for round i appear before any of the round i +1 games. Within a round, games are ordered so the next game is the one involving the highest ranked player left who hasn't yet played in that round. For instance, if players P1, P2, P4, P7, P8, P11, P13 and P17 are still in the tournament and the games for the round are {P2, P4}, {P8, P13}, {P1, P17} and {P7, Pu} then they would be listed in the order 1. {P1, P17} (P1 is the highest ranked player), 2. {P2, P4} (p2 is the next highest ranked player left), 3. {P7, Pu} (p7 is ranked higher than ps and P13) and 4. {Ps, P13} Clearly every schedule can be transformed into a canonical schedule by sorting the games appropriately. 3 1. [3 marks] Prove that minimizing the total boredom of a schedule is the same as minimizing the sums of the rankings of each game's winner. 2. [8 marks] Using your result from question 2.1, prove that if there is a canonical schedule that has the same first k games as the schedule produced by our algorithm, then there is a canonical schedule that has the same first k +1 games as the schedule produced by our algorithm, and whose total boredom is at most that of S. 3. [3 marks] Prove that the algorithm given in the midterm solutions and reproduced at the beginning of this question produces a schedule with minimum total boredom. 2 Boredom and single-elimination tournaments revisited In this question, we revisit a problem you will undoubtedly remember from the midterm. A single- elimination tournament is one where players are paired up, and the winner of each game advances to the next round while the loser is eliminated. The n players are assigned slots numbered from 1 to n. In the first round, the player in slot 1 plays the player in slot 2, the player in slot 3 plays the player in slot 4, etc. The winner of the players in slots 1 and 2 will be assigned slot 1 for the next round, the winner of the players in slots 3 and 4 will be assigned slot 2 for the next round, etc. This is illustrated below: the players are named A through H, and the subscript represents the slot number for each round of the competition. A . D ES F G H round 1 round 2 B C E H. round 3 . H The organizers of the World Only-Relate championship want to make their tournament as exciting as possible and so are looking for a way to pair the contestants up to minimize the total boredom of the games of the tournament. They decide to calculate "boredom" as follows: They give each of players P1, P2, ... Pn a ranking r(Pi) that denotes how good player p; is: r(Pi) >r(pj) if player Pi is better than player Pj. Every time a player pi plays against a player Pj, the game generates a boredom equal to the difference between the players' rankings: Ir(Pi) - r(;). The total boredom is the sum of the boredoms of the individual games. On the midterm you assumed that n is a power of 2, and designed a greedy algorithm that takes in a list of n players with their rankings, and assigns a slot to each player so as minimize the sum of the boredom of the games of the tournament's schedule, assuming that whenever two players play each other, the best of the two always wins. The solution we gave can be summarized as follows: Sort the players by ranking increasing or decreasing) and assign slots based on the players' positions on the sorted list. That is, the worst player gets slot 1, the 2nd worst player gets slot 2, etc. To simplify the notation, we assume without loss of generality that r(Pl) > r(P2) > ... >r(Pn). A tournament schedule is a list of the games for the tournament, and it will be called canonical if All games for round i appear before any of the round i +1 games. Within a round, games are ordered so the next game is the one involving the highest ranked player left who hasn't yet played in that round. For instance, if players P1, P2, P4, P7, P8, P11, P13 and P17 are still in the tournament and the games for the round are {P2, P4}, {P8, P13}, {P1, P17} and {P7, Pu} then they would be listed in the order 1. {P1, P17} (P1 is the highest ranked player), 2. {P2, P4} (p2 is the next highest ranked player left), 3. {P7, Pu} (p7 is ranked higher than ps and P13) and 4. {Ps, P13} Clearly every schedule can be transformed into a canonical schedule by sorting the games appropriately. 3 1. [3 marks] Prove that minimizing the total boredom of a schedule is the same as minimizing the sums of the rankings of each game's winner. 2. [8 marks] Using your result from question 2.1, prove that if there is a canonical schedule that has the same first k games as the schedule produced by our algorithm, then there is a canonical schedule that has the same first k +1 games as the schedule produced by our algorithm, and whose total boredom is at most that of S. 3. [3 marks] Prove that the algorithm given in the midterm solutions and reproduced at the beginning of this question produces a schedule with minimum total boredom