Assignment:
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).
Provide complete and step by step solution for the question and show calculations and use formulas.