This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5.
Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there exists a set of boys’ and girls’ preferences such that every dating arrangement is stable.
As I understand it, this is asking for a set of preferences such that any combination of matchings is stable.
Informally, my thought was to show by contradiction this is not possible. I assume the theorem is true, then there must be some combination such that every male is paired with his least favorite partner. In this case, assuming the theory holds, then every female must prefer their partner the most. Otherwise, if any female prefered any other male more, they would form a rogue couple. This then would be true starting with the female set, that is there exists a combination such that each female is paired with her least favorite, so each male must like his partner the most.
Given this, and that we are looking at every combination, there must exist a combination of two couples such that a male is with his least favorite and a female is with her least favorite (who are different people because of the idea above). This would create a non-stable matching, so there is a contradiction.
I feel this is wrong somehow, and that I am missing something obvious. Would someone point me in the right direction?
I am sorry if this is way off base or too informal, I do not have a background in math, and trying to teach myself has been fun but slow going without anyone to consult.