Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are two rooms (A and B) and $n$ people.

Each person i in $[1,n]$ supplies two non-negative numbers: $A_i$ and $B_i$, such that $A_i+B_i=n$.

The number $A_i$ can be interpreted as saying "I am willing to be in room A as long as there are at most $A_i$ people in it", and similarly $B_i$ for room B.

Now, we want to put $k$ people in room A, and $n-k$ people in room B, such that:

  • For each person $i$ in room A: $A_i \geq k$
  • For each person $j$ in room B: $B_j \geq n-k$

Is this always possible? If so, what is the way to find $k$?

Additionally, I will be happy to know if this question has a general name, or is a part of a general theory.

Thanks!

share|improve this question

1 Answer 1

up vote 6 down vote accepted

A greedy approach will work. Take the person $i$ with the highest $A_i$, i.e. the most willing to go to A. If they fit in A, put them there; everyone else in A was at least as willing, so they're all still content. Continue until you reach a person who can't fit in A.

Now, you've put $k$ people in room A. Everyone remaining has $A_j \leq k$, and therefore $B_j \geq n-k$. Thankfully, there are only $n-k$ of them. So put them all in B, and we're done!

(Sorry, I'm not aware of a general theory.)

share|improve this answer
    
Thank you! This solution seems to generalize to any number of rooms. –  Erel Segal Halevi Aug 8 '13 at 5:40

Your Answer

 
discard

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.