 Generalized pigeonhole principle

For $N$ objects assigned to $m\ge 1$ boxes, let $n_i$ be the number in box $i$. The generalized pigeonhole principle statesThe ceiling function rounds up because box counts are integers. An equivalent threshold formulation says: for a positive integer $k$, if $N>m(k-1)$, some box contains at least $k$ objects. For $N=m(k-1)$, putting $k-1$ objects in each box shows why the strict inequality matters. ^[ref]

Computed examples. For $N=13$ and $m=12$, $\lceil 13/12\rceil =2$. Counts $(2,1,1,1,1,1,1,1,1,1,1,1)$ attain this bound. For $N=23$ and $m=7$, $\lceil 23/7\rceil =4$, and the balanced counts $(4,4,3,3,3,3,3)$ sum to $23$ and have largest count exactly $4$. The threshold version agrees: $23>7(4-1)=21$. In contrast, seven boxes each containing three hold only $21$ objects.

The bound is sharp for every $N$ and $m$. Use Euclidean division to write $N=qm+r$ with integers $q\ge 0$ and $0\le r<m$. Place $q+1$ objects in each of $r$ boxes and $q$ objects in each remaining box. The largest count is $q+1$ if $r>0$, and $q$ if $r=0$, exactly $\lceil N/m\rceil$. This balanced arrangement makes the guarantee best possible even though other arrangements can be much more crowded.

Proof outline. If every count were at most $k-1$, the total would be at most $m(k-1)$. This contradicts $N>m(k-1)$. Taking $k=\lceil N/m\rceil$ proves the displayed bound for $N>0$; for $N=0$ every count is zero.