Hi, This is a Algorithm question. Thank you for your help.

As for the 2c, you can assume n is a natural number. The question does not really make much sense if n is a fraction or a negative number.

Problem 2. Stable Matching In class we showed that given any set of rankings for n doctors and n hospitals, there always exists at least one stable matching of doctors and hospitals. (a) Show that there is a set of rankings for 2 doctors and 2 hospitals such that there is a unique stable matching. Justify the claim that there is a unique stable matching. Solution: b) Show that there is a set of rankings for 2 doctors and 2 hospitals such that there exist two distinct stable matchings. Solution: (c) Show that, for every n, there is a set of rankings for 2n doctors and 2n hospitals such that there are at least 2" distinct stable matchings. Hint: start with your answer to part (b) and build your ranking two pairs at a time. Solution: Problem 2. Stable Matching In class we showed that given any set of rankings for n doctors and n hospitals, there always exists at least one stable matching of doctors and hospitals. (a) Show that there is a set of rankings for 2 doctors and 2 hospitals such that there is a unique stable matching. Justify the claim that there is a unique stable matching. Solution: b) Show that there is a set of rankings for 2 doctors and 2 hospitals such that there exist two distinct stable matchings. Solution: (c) Show that, for every n, there is a set of rankings for 2n doctors and 2n hospitals such that there are at least 2" distinct stable matchings. Hint: start with your answer to part (b) and build your ranking two pairs at a time. Solution