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.
It looks like you're looking for more than you need here. You can go about it directly: given any set of preferences there exists a matching that is not stable.
What you need is only to find one combination of boy and girl such that the boy is not the girl's least favorite partner, and the girl is not the boy's least favorite partner. Then, in order to create a non-stable matching, just pair each of those two up with their least favorite partner, and then match up everyone else randomly.
The only thing you need, then, is to be sure that there is such a couple for any set of preferences where $n\ge 3$. A simple counting argument will succeed in that ...