The pigeon-hole principle
Master the pigeon-hole principle in Year 11 VCE Specialist Mathematics. It says that placing \(n\) items into \(m\) boxes forces some box to hold at least \(\left\lceil\dfrac{n}{m}\right\rceil\) items, so with more items than boxes at least one box must double up. It sits in the Discrete mathematics area of study of the VCE Mathematics Study Design (VCAA), within the Combinatorics topic of Unit 1.
You will learn the basic form (\(n>m\) forces a box of \(2\)), the generalised form \(m(k-1)+1\) that guarantees a box of \(k\), and how to build existence proofs — shared birth months, matching socks and equal remainders.
Theory
The pigeon-hole principle says that if \(n\) items are placed into \(m\) boxes, then some box must hold at least \(\left\lceil \dfrac{n}{m}\right\rceil\) items. In its basic form, if \(n>m\) then some box holds at least \(2\). In Year 11 Specialist Mathematics you use it to guarantee a result and to build existence proofs — shared birth months, matching socks, and equal remainders.
The pigeon-hole principle is a simple counting idea with surprising reach. If more pigeons are placed into fewer pigeon-holes than there are pigeons, then at least one hole must contain more than one pigeon. The “pigeons” are the items being sorted and the “holes” are the categories they fall into.
In its basic form: if \(n\) items are placed into \(m\) boxes and \(n>m\), then at least one box contains at least \(2\) items. The reasoning is by the worst case — if every box held at most one item, the boxes could hold at most \(m\) items in total, but there are \(n>m\) of them, so some box must double up.
More precisely, sharing \(n\) items as evenly as possible across \(m\) boxes still forces some box to hold at least \(\left\lceil \dfrac{n}{m}\right\rceil\) items, where \(\lceil\ \rceil\) is the ceiling (round up). This is the guaranteed load.
Read the other way, this becomes the generalised form: to be certain that some box holds at least \(k\) items, you must place a minimum of \(m(k-1)+1\) items. Filling every box to \(k-1\) uses \(m(k-1)\) items without any box reaching \(k\); the very next item is the one that forces a box to \(k\). The heart of every problem is naming the pigeons and the holes correctly.
Place \(n\) items into \(m\) boxes. The guaranteed load — the largest number some box is certain to hold — is the ceiling of \(n\) divided by \(m\):
The basic form is the case \(k=2\): as soon as there are more items than boxes, the ceiling is at least \(2\).
Turned around, the generalised form gives the least number of items that guarantees some box holds at least \(k\):
The two forms are inverses of each other. Given \(n\) and \(m\), the ceiling gives the forced load; given the target load \(k\) and the number of boxes \(m\), the formula \(m(k-1)+1\) gives the number of items needed to force it.
How to apply the pigeon-hole principle
- Name the pigeons and the holes. Decide what is being sorted (the items / pigeons) and what the categories are (the boxes / holes). This is the whole problem — get it right and the arithmetic is short.
- Count the holes \(m\). For months \(m=12\); for sock colours \(m=\) the number of colours; for remainders on division by \(d\), \(m=d\) (the remainders \(0,1,\dots,d-1\)).
- Decide which way round the question runs. Given the items, find the forced load \(\left\lceil \tfrac{n}{m}\right\rceil\). Given a target load \(k\), find the least number of items \(m(k-1)+1\).
- Argue by the worst case. Spread the items as evenly as possible (or fill each box to \(k-1\)); the item that has nowhere left to go proves the result.
To guarantee two people share a birth month there are \(m=12\) holes, so a minimum of \(12(2-1)+1 = 13\) people is needed.
Identify the pigeons and the holes, then take the ceiling of their ratio:
| \(\text{pigeons } n\) | \(=\) | \(20\) |
| \(\text{holes } m\) | \(=\) | \(6\) |
| \(\left\lceil \dfrac{n}{m}\right\rceil\) | \(=\) | \(\left\lceil \dfrac{20}{6}\right\rceil\) |
| \(=\) | \(\lceil 3.33\ldots\rceil\) | |
| \(=\) | \(4\) |
Some box must hold at least \(4\) pigeons.
The holes are the \(12\) months; the people are the pigeons:
| \(\text{holes } m\) | \(=\) | \(12 \ \text{(months)}\) |
| \(\text{worst case: one person per month}\) | \(=\) | \(12 \ \text{people, all different}\) |
One more person must repeat a month \(\bigl(k=2\bigr)\):
| \(n\) | \(=\) | \(m(k-1)+1\) |
| \(=\) | \(12(2-1)+1\) | |
| \(=\) | \(13\) |
\(13\) people guarantee two share a birth month.
The colours are the holes; a matching pair means some hole reaches \(k=2\):
| \(\text{holes } m\) | \(=\) | \(3 \ \text{(colours)}\) |
| \(\text{worst case: one of each colour}\) | \(=\) | \(3 \ \text{socks, all different}\) |
The next sock must repeat a colour:
| \(n\) | \(=\) | \(m(k-1)+1\) |
| \(=\) | \(3(2-1)+1\) | |
| \(=\) | \(4\) |
\(4\) socks guarantee a matching pair.
Fill each box to \(k-1\), then one more forces a box to \(k\); here \(k=3\):
| \(\text{boxes } m\) | \(=\) | \(5\) |
| \(\text{worst case: } (k-1)=2 \text{ per box}\) | \(=\) | \(5\times 2 = 10 \ \text{cards}\) |
The next card forces some box to \(3\):
| \(n\) | \(=\) | \(m(k-1)+1\) |
| \(=\) | \(5(3-1)+1\) | |
| \(=\) | \(11\) |
\(11\) cards are required.
The holes are the \(5\) possible remainders; a repeat means \(k=2\):
| \(\text{holes } m\) | \(=\) | \(5 \ \text{(remainders } 0\text{--}4)\) |
| \(\text{worst case: one integer per remainder}\) | \(=\) | \(5\) |
The next integer must repeat a remainder:
| \(n\) | \(=\) | \(m(k-1)+1\) |
| \(=\) | \(5(2-1)+1\) | |
| \(=\) | \(6\) |
\(6\) integers guarantee a repeated remainder.
Now the target load is \(k=3\) with \(m=12\) month-holes:
| \(\text{months } m\) | \(=\) | \(12\) |
| \(\text{worst case: } 2 \text{ per month}\) | \(=\) | \(12\times 2 = 24 \ \text{people}\) |
One more person forces a third into some month:
| \(n\) | \(=\) | \(m(k-1)+1\) |
| \(=\) | \(12(3-1)+1\) | |
| \(=\) | \(25\) |
\(25\) people guarantee three sharing a birth month.
Common pitfalls
Frequently asked questions
What is the pigeon-hole principle?
It states that if \(n\) items are placed into \(m\) boxes, some box must contain at least \(\left\lceil \tfrac{n}{m}\right\rceil\) items. In particular, if there are more items than boxes \((n>m)\), then at least one box holds \(2\) or more.
What is the basic form of the principle?
The basic form is the case \(k=2\): if \(n>m\), then at least one box must contain at least \(2\) items. If every box held at most one item there could be at most \(m\) items, but there are \(n>m\), so some box doubles up.
What is the generalised form?
To guarantee that some box holds at least \(k\) items, you need a minimum of \(m(k-1)+1\) items. Filling each of the \(m\) boxes to \(k-1\) uses \(m(k-1)\) items with no box at \(k\); the next item forces one box to \(k\).
How do I know how many pigeons force a shared box?
Work out the number of holes \(m\) and the target load \(k\), then use \(m(k-1)+1\). To guarantee two people share a birth month, \(m=12\) and \(k=2\), giving \(12(2-1)+1=13\) people.
How does it apply to remainders?
When integers are divided by \(d\) the possible remainders are \(0,1,\dots,d-1\), so there are \(d\) holes. Choosing \(d+1\) integers forces two to share a remainder — for \(d=5\), any \(6\) integers include two with the same remainder.
When do I round up rather than down?
Always round up. The guaranteed load is \(\left\lceil \tfrac{n}{m}\right\rceil\), the ceiling of \(n/m\). Even the most even split leaves some box holding the rounded-up value, so \(\tfrac{20}{6}=3.33\ldots\) rounds up to a guaranteed \(4\).