Question

Men, women and yupi live on the planet Alphaomega. Their family pattern is a triple that consists of a man, a woman and a yupi. Three sets are given: M includes n men, W includes n women and Y includes n yupi. A matching is a set H of ordered triples of the form (m, w, y) with the property that each member of M, each member of W and each member of Y appears in at most one triple from H. A matching H is called perfect if each member of M, each member of W and each member of Y appears exactly in one triple from H. Assume that each man ranks all women and all yupi, each woman ranks all men and all yupi, and each yupi ranks all women and all men. Two triples (m, w, y) and (m’, w’, y’) form an instability in a matching H if one of the following conditions is true:

(1) m prefers w’ to w and w’ prefers m to m’

(2) m prefers y’ to y and y’ prefers m to m’

(3) y prefers w’ to w and w’ prefers y to y’

A matching H is called stable if it does not have instabilities. Decide whether the following statement is true or false.

There is an algorithms that solves the Stable Matching Problem for every instance of this problem.

If it is true, design an algorithm for building a stable perfect matching. Note that when you design an algorithm, you have to prove that it solves the necessary problem If it is false, give a counterexample.

The link above has a solution by someone from Chegg but I don't understand how he's right. I commented their solution by saying I don't understand how they prove the statements to be false, yet say it's still a stable matching and that's it's possible to solve it. Can you please look over the question above and give me a more thorough explanation?

Thank you

Answer 1