0
$\begingroup$

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\}$"?

3 Answers 3

1

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.

  • 0
    @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.2012-09-23
1

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.

1

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.