# How should I understand “partitioned into $k$ classes with quotas $\{p_i\}$”?

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

-

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.

-
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.
-

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.

-