The Problem The chess teams of two schools, University of Y (henceforth just called Y) and Z University (henceforth just called Z), will be having a contest next week. Each team has n players, and the contest will consist of n matches. Before the contest starts, the coach of each team submits a schedule, assigning each of their players to exactly one match. As for the players, all university players across the country are uniquely ranked (i.e. no ties), with a rank of 1 denoting the best player. During a match the better-ranked player always wins. Before presenting the problems, a quick word on notation: The notions of a "higher" or "lower"-ranked player is ambiguous in this context. In other words, it may be hard to tell if a "higher"-ranked player refers to the player with a higher number ranking, meaning they're worse at chess, or if it refers to a better chess player. We avoid this by strictly using the words "better", "worse", "best", and "worst" to compare player rankings. In your proofs, we encourage you to stick to this as well, or to clearly indicate which convention you plan to follow. You will explore the concept of stability in this problem. Specifically, suppose the coach for Y submits schedule S, and the coach for Z submits schedule T. If neither coach can change their schedule-while keeping the other schedule the same- and win more games, then the pair of schedules (S,T) is said to be stable. Here is an example with n=3: Y has players Yoda, Yoshi, and Yerrr, who are ranked 1, 3 and 6, respectively. Z on the other hand, has players Zendaya, Zion, and Zubat, who are ranked 15, 24, and 88, respectively. The coach for Y submits the schedule S = Yoda, Yoshi, Yerrrand the coach for Z submits the schedule T= [Zendaya, Zubat, Zion), where the i-th element in the list denotes the player assigned to the i-th match. For this pair of schedules, Y wins all 3 matches. If either coach changes her/his schedule (while keeping the other the same), it will still be the case that Y wins all 3 matches. Thus, (S,T) is stable. In fact, it is easy to see that with these player rankings, all possible pairs of schedules are stable. The corresponding question to the one we asked in class is the following: For a given set of n players and their corresponding rankings, does there exist at least one stable pair of schedules? Here are the two parts: Part (a) Show that the answer is yes for the following special case the worst-ranked player at Y is better than the best-ranked player at Z. Part (6) Show that the ans is no for the general In other wo show that there exists a set of players and their corresponding rankings, for which there does not exist any stable pair of schedules. Note It is helpful for part (b) to formally write down in first order logic, what the problem is asking for. To help you guys out, here is an overview of what you need to do: You have to present only one input and then prove that every possible pair of schedules (S, T) is NOT stable. Q. Hint Note that for any given n, there are (n!)2 many possible pairs of schedules (S,T) Common Mistake A common mistake for part (b) is to present an example and then argue that some but not all (n!) schedules are not stable. The Problem The chess teams of two schools, University of Y (henceforth just called Y) and Z University (henceforth just called Z), will be having a contest next week. Each team has n players, and the contest will consist of n matches. Before the contest starts, the coach of each team submits a schedule, assigning each of their players to exactly one match. As for the players, all university players across the country are uniquely ranked (i.e. no ties), with a rank of 1 denoting the best player. During a match the better-ranked player always wins. Before presenting the problems, a quick word on notation: The notions of a "higher" or "lower"-ranked player is ambiguous in this context. In other words, it may be hard to tell if a "higher"-ranked player refers to the player with a higher number ranking, meaning they're worse at chess, or if it refers to a better chess player. We avoid this by strictly using the words "better", "worse", "best", and "worst" to compare player rankings. In your proofs, we encourage you to stick to this as well, or to clearly indicate which convention you plan to follow. You will explore the concept of stability in this problem. Specifically, suppose the coach for Y submits schedule S, and the coach for Z submits schedule T. If neither coach can change their schedule-while keeping the other schedule the same- and win more games, then the pair of schedules (S,T) is said to be stable. Here is an example with n=3: Y has players Yoda, Yoshi, and Yerrr, who are ranked 1, 3 and 6, respectively. Z on the other hand, has players Zendaya, Zion, and Zubat, who are ranked 15, 24, and 88, respectively. The coach for Y submits the schedule S = Yoda, Yoshi, Yerrrand the coach for Z submits the schedule T= [Zendaya, Zubat, Zion), where the i-th element in the list denotes the player assigned to the i-th match. For this pair of schedules, Y wins all 3 matches. If either coach changes her/his schedule (while keeping the other the same), it will still be the case that Y wins all 3 matches. Thus, (S,T) is stable. In fact, it is easy to see that with these player rankings, all possible pairs of schedules are stable. The corresponding question to the one we asked in class is the following: For a given set of n players and their corresponding rankings, does there exist at least one stable pair of schedules? Here are the two parts: Part (a) Show that the answer is yes for the following special case the worst-ranked player at Y is better than the best-ranked player at Z. Part (6) Show that the ans is no for the general In other wo show that there exists a set of players and their corresponding rankings, for which there does not exist any stable pair of schedules. Note It is helpful for part (b) to formally write down in first order logic, what the problem is asking for. To help you guys out, here is an overview of what you need to do: You have to present only one input and then prove that every possible pair of schedules (S, T) is NOT stable. Q. Hint Note that for any given n, there are (n!)2 many possible pairs of schedules (S,T) Common Mistake A common mistake for part (b) is to present an example and then argue that some but not all (n!) schedules are not stable