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.

I read the following statement in Introduction to Graph Theory by Douglas B. West:

If $\sum{p_i}-k+1$ objects are partitioned into $k$ classes with quotas $\{p_i\}$, then some class must meet its quota.

Several search on Google returns nothing satisfying. I don't understand what this statement means: how should I understand "partitioned into $k$ classes with quotas $\{p_i\}$"?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

You’re going to divide a bunch of objects into $k$ classes, $C_1,\dots,C_k$. You’ve assigned a desired quota to each class: you’d like to have at least $p_i$ objects in class $C_i$. Suppose that every class fails to meet its quota. Then for each $i=1,\dots, k$, class $C_i$ can have at most $p_i-1$ objects. The total number of objects is then at most

$$\sum_{i=1}^k(p_i-1)=\left(\sum_{i=1}^kp_i\right)-k\;;$$

if you have more objects than this, at least one class must meet its quota, meaning that there is at least one $i$ such that $C_i$ has $p_i$ (or more) objects. Thus, if you have at least

$$\left(\sum_{i=1}^kp_i\right)-k+1$$

objects, some class must meet its quota.

share|improve this answer
    
As I understand, assigning quota $p_i$ to class $C_i$ means one wants the size of $C_i$ to be at least $p_i$ according to your answer? –  Jack Sep 23 '12 at 22:38
    
@Jack: Yes. And you’re looking for a condition on the number of objects that guarantees that at least one class will meet its quota. You’re not trying to guarantee that every class so: no matter how many objects you have, you can’t guarantee that. –  Brian M. Scott Sep 23 '12 at 22:43

Suppose $p_1=5, p_2=2, p_3=7.$ Then if there are 5+2+7-3+1=12 (or more) objects grouped into three classes, then at least one of the following is true:

  • The first group has at least 5 members.
  • The second group has at least 2 members.
  • The third group has at least 7 members.
share|improve this answer

This appears to be a variant of a pigeonhole argument. By "quota" is meant a cap (maximum) on objects assigned. If each class is assigned at most one less than its quota, the total assigned objects is at most $\sum_{i=1}^k (p_i - 1)$, and not all of the objects can be assigned since there are more than that.

share|improve this answer

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.