The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, GMAT, AMC-8, AMC-10, Math Kangaroo 5-6, Math Kangaroo 7-8, Math Kangaroo 9-10.

The pigeonhole principle was formulated by the German mathematician Lejeune Dirichlet:

If we attempt to place n objects into m boxes and n>m, then there is __at least__ one box in which we will have to place __at least__ 2 objects.

Example:

In a family of 7 people, Santa has brought 8 presents. The immediate logical conclusion is that there is at least one person who received more than one present.

Example:

In a set of 5 numbers chosen at random, there are at least two numbers that give the same remainder when divided by 4.

Since there are only 4 possible remainders when dividing any number by 4: 0,1,2 or 3, the randomly chosen numbers can be placed in any of 4 boxes, according to their remainder upon division by 4. Since there are more than 4 numbers, two of them will have to have the same remainder regardless of how they are chosen.

The most difficult part in solving a problem using the Pigeonhole principle is making the choice of objects and boxes. Some of the most difficult problems on the IMO use this principle, but the choice of boxes and objects is not at all obvious and requires cleverness and knowledge of mathematics.

The SAT I and the GMAT use only the simplest examples.

Look for more complicated situations in competitive mathematics.