Recent content by Mikazzum

Evgeny, i think this problem is NP complete. I agree P vs NP is way beyond my capability. I hope to see it proved one way or another one day. I don't know if it is beyond the capability of this forum as I am a newbie and there seem to be some pretty good math brains here!

Thanks Mark. Sorry I mis posted

I do not have a solution to this problem. It is a massive problem well beyond my capabilities. I am nevertheless fascinated by it! The above text is how I would begin this. But I do not know how to progress this further.

Sorry Evgeny, I should have articulated better. The problem is that you have 400 students but only 100 of them can have rooms in a dorm. But the dean has complicated matters by giving you pairs of students who are not compatible. You have to come up with a list of 100 students from the 400 which...

Can I start like this? The math is trivial, just a conjecture. Create a subset of incompatible pairs of students which only names any student once. Put the resulting pairs in two columns. Pick successful room winners by choosing all of either of the columns. Assuming that creates less than 100...