Pigeonhole principle

Last updated on 9/15/25

Perhaps the very first idea I was introduced to when learning about the Putnam was the Pigeonhole principle. The idea itself is pretty intuitive and generally reads as follows:

Suppose there are \(n+1\) items that must be distributed into \(n\) bins. At least one bin contains two or more items.

This principle is one that most everyone subconsciously follows on their day to day; if you have three apples and you only have two baskets, of course one of the baskets will contain at least two of the apples. Although a simple principle, it has its applications to the Putnam. Let’s look at some examples.

Examples

Putnam 2002 A2. Given any five points on a sphere, show that some four of them must lie on a closed hemisphere.

Recall that for any two points on a sphere, there is a unique great circle (a circle on the sphere that has the same radius of the sphere) that connects them, splitting the sphere in half. Picking any two of the five points to be on a great circle leaves three points to be distributed between two hemispheres. By the pigeonhole principle, two of these points must lie on the same hemisphere, and therefore four points must lie on the same closed hemisphere (two on the edge + two on the "face"). Of course, more than two points can lie on the same great circle in which case the property is automatically true.