In this exercise we consider a situation with n men and n women.
(a) Prove that if in stage t of the men's courtship algorithm, a particular man is dismissed for the (n - 1)-th time, then the algorithm terminates at stage (t + 1).
(b) Prove that the men's courtship algorithm terminates after at most (n - 1)2 + 1 stages.
(c) Find preference relations under which the algorithm terminates after precisely (n - 1)2 + 1 stages (hence this is the lowest bound for the length of the algorithm).