The Pigeonhole Principle – Peter’s Blog

The pigeonhole principle is based on a very simple idea but is very powerful in mathematical problem solving. Here is the principle:

Pigeonhole Principle: If there are $nm+1$ objects to be placed in $n$ boxes, then at least one box must contain at least $m+1$ objects.

The proof is straightforward. We can proceed by contradiction. Specifically, if the conclusion is false then it means that each of the boxes has at most $m$ objects. Since there are $n$ boxes, we have at most $mn$ objects to begin with. But this contradicts with the assumption that there are $nm+1$ objects.

A specific instance of this is if $m=1$ so that we have $n+1$ objects in $n$ boxes. The pigeonhole principle implies that at least one box has at least 2 objects. This can be applied in the following problem:

Suppose $n+1$ distinct integers are picked from the set $\{1,2,\ldots,2n-1,2n\}.$ Show that two of the integers must sum to $2n+1$ .

A tidy solution comes from the specific instance of the pigeonhole principle cited above. Specifically, consider $n$ boxes labelled as $\{1,2n\}, \{2,2n-1\}, \ldots, \{n,n+1\}$ . For each integer picked, put it in the box labelled with it. The pigeonhole principle says at least one box will have at least 2 objects in it. In fact, for any such box, it will have exactly 2 objects in it as there are only 2 integers on the label of each box. The proof is complete on noticing that these two integers sum to $2n+1$ .