The pigeonhole
principle relies on filling existing spaces (pigeonholes,
boxes, envelopes, and the like) with items (pigeons, coins,
letters, and so on) to the point where all spaces are
just one item short of being full. At this point, no
matter where the next item is placed, we get a full box. The
variables here are the number of spaces to fill and
the number of items required in each space to assure that
space is full.
A generalization of the situations we
have considered is the following:
Let n represent the number of spaces to
fill and use to
represent the number of items needed for each of the n
spaces to be considered full. Then to reach the point where
each of the n spaces are just one item short of being
full, we need this many items:
The next item we add, no matter where we
put it, will create a full space. Therefore, the number of
items needed to assure that at least one of the n spaces is
full is.
