Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a college dorm two students share a single room. Each student is asked to give two names of preferred roommates. Housing ensures that if a student is on the preferred list of some other student then the second student is also on the preferred list of the first student.

Prove that it is always possible to pair the students such that everyone's roommate is from the preferred list.

So say Student A has (B,C) as preferred roommates, so B would be on the preferred list of A - now "some other student", would that mean that if there is this other student D then ???

Honestly I don't understand what the question is trying to say - how to even set this up. I do realize that this would have to do with matching - perhaps some sort of alternating graph.

Any help would be greatly appreciated.

share|cite|improve this question
up vote 3 down vote accepted

It doesn't even seem to be true. Suppose the students are Adam, Brian, Charles, Dan, Eric and Fred:

  • Adam, Brian and Charles are friends and each prefers the two others.
  • Dan, Eric and Fred are friends and each prefers the two others.

Since each friend clique has an odd number of students in them, at least one room has to be shared by students from different cliques -- but those will not have preferred each other.

share|cite|improve this answer
Turns out there was a mistake in the question. Your solution found that mistake. – Relative0 Jun 8 '13 at 17:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.