[superprismatic]

Suppose we have a group of N men and another group

of N women. Each man makes a preferential list of

women he could marry (ties are not allowed). Similarly,

each woman makes a preferential list of men she could

marry. It is always possible to pair up all of these

people into N man-woman pairs so that the pairing is

stable. By stable I mean that, if we take any two

pairs in this pairing, (m1,w1) and (m2,w2) say,

then it is never the case that [m1 would prefer w2

over w1] AND [w2 would prefer m1 over m2]. That is,

it is never the case that m1 and w2 would both prefer

each other to their paired partners. An easy proof

of this can be found at:

http://tinyurl.com/nze7cr

If, however, we have to pair up 2N people to be

roommates, that's a different matter! If each of

these people make a preferential list of possible

roommates (of all 2N-1 other people -- with no ties),

then it is not always possible to make a stable pairing

according to the definition above. What is the smallest

N(>2) such that a stable pairing is not always possible?

For your value of N, give a preferential order (1

being most preferable to 2N-1 being least preferable)

for each of the 2N people, for which a stable pairing

cannot be made.

[Guest]

i posted a similar problem a while ago. No one ever bit.

I'll leave it for someone else