(Please give explanation.)
In the stable marriage algorithm described in class, the men propose to the women in preference order, and each woman accepts the best proposal she has seen so far.
If there are n men and n women, how many women (as a function of n) can be forced to settle for their last choice?
Describe a scenario that would cause this many women to be matched with last-choice men: what preference orderings cause this behavior, and what does the algorithm do when given this input?