1. y == 4 (mod 9). Since x+5 == 1 (mod 9), we can add 4 to both
sides and conclude that x == 5 (mod 9). Since y == x^2 - x + 2 (mod 9),
we can substitute in for x and conclude that y == 5^2 - 5 + 2 == 22
== 4 (mod 9). Hence y can be any integer that is congruent to 4
modulo 9 (i.e., ..,-14,-5,4,13,22,...).
2. Yes. Since there are more men than women, there is some man, call
him Bob, who ends up with no wife. This means Bob proposed to but was
rejected by both women. Since once someone proposes to a woman, we are
guaranteed she will forever thereafter have some man on a string (by
the Improvement Lemma), when the algorithm terminates, both women have
someone on a string. This means that both women will find a husband.