The pigeonhole principle is attributed to Peter Gustav Lejeune Dirichlet, and its premise is common sense. Nonetheless, this seemingly trivial revelation is a powerful tool in combinatorics as well as in proving strong statements about collections without having to consider each element of a collection.
Definition
Let
n
and
k
be positive integers, and let
n>k
. Suppose we have to place
n
identical balls into
k
identical boxes, where
n>k
. Then there will be at least one box in which we place at least two balls.
Example
Aside: Integer Partition
We will use the function IntegerPartitions to “distribute” the number of balls into the exact number of boxes, by partitioning the integer balls into evenly boxed parts.
To give an example of an integer partition, see that IntegerPartitions[4] yields a list of lists containing integers where the sum of those integers is 4.
In[]:=
IntegerPartitions[4]
Out[]=
{{4},{3,1},{2,2},{2,1,1},{1,1,1,1}}
The latter can be shown by applying the function Plus to each sublist that is returned by IntegerPartitions[4].
In[]:=
Plus@@@IntegerPartitions[4]
Out[]=
{4,4,4,4,4}
Thus we see that an integer partition of the integer
n
into a list of length
k
is equivalent as distributing
n
balls into
k
boxes. Using the optional argument
{k}
, we can specify that we want integer partitions of exactly
k
parts.
Applying the Pigeonhole Principle
Here we will see that if we try to distribute 10 balls among 4 boxes, there will be a box with at least 2 balls:
In[]:=
balls=10;boxes=4;
Using IntegerPartitions (as described above), we can find all the ways to distribute 10 balls among 4 boxes:
, such a bar chart will be impractical to look at. Let us use AllTrue to show that the max value for each possible way to distribute the balls among boxes is, in fact, greater than or equal to 2!