Brazilian Mathematical Olympiad

In round $k$ each unpaired boy $B$ in turn proposes to the girl $G$ he ranks highest amongst those he has not yet proposed to. If $G$ is not yet paired, or if she prefers $B$ to the boy she is currently paired with, then we pair $B$ and $G$ (and remove any existing pair for $G$). We claim that this algorithm terminates and gives a stable pairing.

First we must establish that it terminates. Each boy can propose to at most $n$ girls and in each round at least one boy must make a proposal, so it must terminate in $n^2$ rounds or less.

Second we must establish that it results in every boy and girl being paired off. Once a girl is paired, she always remains paired, although not necessarily to the same boy. Suppose girl $G$ ends up unpaired. Since there are equal numbers of boys and girls, a boy $B$ must also end up unpaired. By the end $B$ must have proposed to every girl, including $G$. Hence $G$ must have been paired at the end of that round. Contradiction.

Finally, we must establish that the pairing is stable. Suppose not, so that we end up with pairs $(B, G)$ and $(B', G')$, where $B$ prefers $G'$ to $G$ and $G'$ prefers $B$ to $B'$. Since $B$ prefers $G'$ to $G$ he must have proposed to $G'$ before $G$. At the end of that round either $B$ and $G'$ were paired, or $G'$ was paired to $B''$ whom she preferred to $B$. In the first case, we have a contradiction because a girl can only change her pairing in favor of someone she prefers. So if she ends up paired to $B'$ having earlier been paired to $B$, then she must prefer $B'$ to $B$. Contradiction. In the second case, $G'$ must prefer $B''$ to $B$ and $B'$ to $B''$. Again a contradiction. So the pairing is stable.