In class $($and in the textbook$),$ we saw an example of a stable matching instance in which there are

two different stable matchings. Building on this idea, give a class of instances such that for every k$,$

you have an instance that has at least k distinct stable matchings. Explain clearly what these different

stable matchings are, and why they are stable.

$[$Hints: $(1)$ Obviously, as k gets large, your instances will need to contain more men$/$women$.(2)$ The

easiest way to solve this draws heavily on the example from the class$/$textbook$.$ Think powers of two!$]$