The pigeonhole principle

The Pigeonhole Principle: Suppose that \(M>N\) and you put \(M\) balls in \(N\) boxes. Then at least one box has more than one ball.

For our purposes we will treat this as an axiom, since:

  • it seems obvious, and
  • to prove it you have to be very careful about what axioms you are relying on.

The contrapositive version: Suppose that you put \(M\) balls in \(N\) boxes, and no box contains more than one ball. Then \(M<N\).

The pigeonhole principle and functions

Suppose we have a function \(F:A\to B\) where \(A\) and \(B\) are finite sets.

Proposition: If \(|A|>|B|\) then \(F\) is not injective.

Proof: Think of the elements of \(A\) as balls and the elements of \(B\) as boxes. If \(F(a)=b\), then you put ball \(a\) in box \(b\). If \(F\) is injective, then by the definition of injectivity, different balls go in different boxes. Thus no box contains more than one ball. This implies there are at least as many boxes as balls, so \(|B|\ge |A|\). This is a contradiction of our assumption that \(|A|>|B|\), so \(F\) is not injective.

The pigeonhole principle and functions 2

Suppose we have a function \(F:A\to B\) where \(A\) and \(B\) are finite sets.

Proposition: If \(|A|<|B|\), then \(F\) is not surjective.

Proof: Suppose that \(|A|<|B|\) and think of elements of \(A\) as boxes and elements of \(B\) as balls, with \(F(a)=b\) meaning you put ball \(b\) in box \(a\) – the reverse of the above. Suppose \(F\) is surjective. Then every ball – every element of \(B\) – has a corresponding box. But pigeonhole principle says that at least one box has two balls. That is impossible if \(F\) is a function.

Some example applications

Example from page 234.

Proposition: Suppose \(A\) is a set of any \(10\) integers between \(1\) and \(100\). Then there are two subsets \(X\subseteq A\) and \(Y\subseteq A\) such that the sum of the elements of \(X\) is the same as the sum of the elements of \(Y\).

Problem 12.3.5

Proposition: Any set of seven distinct natural numbers contains a pair of numbers whose sum or difference is divisible by \(10\).