Pigeonhole Principle Tutorial

Albert Y. C. Lai, trebla [at] vex [dot] net

Solved Examples

The following examples are not solved by the pigeonhole principle.

  1. 9 holes accomodate 10 pigeons. Show that some hole gets 2 pigeons.

    Solution: Average number of pigeons per hole is

    10/9 > 1.11 > 1

    Some hole must get 2 pigeons or more to pull the average above 1.

  2. An employee receives a paycheck every other week on Fridays. Show that in some month there are 3 paychecks.

    Solution: In a year, there are 12 months and at least 26 paychecks (at least 52 Fridays). Average number of paychecks per month is at least

    26/12 > 2.16 > 2

    Some month must see at least 3 paychecks to pull the average above 2.

  3. The 12 numbers 1 to 12 are permuted and laid out around a circle. Show that some group of 3 adjacent numbers has sum 20 or more.

    Solution: There are 12 groups to consider. (They overlap; that's fine.) To find the average sum per group, first sum up all 12 groups, then divide by 12.

    To sum up all 12 groups, note that each number participates in exactly 3 groups (a group uses it as the left, another group uses it as the centre, and yet another group uses it as the right). So summing up all groups is 3 times summing up the numbers 1 to 12.

    The average sum per group is

    3×(1 + ... + 12)/12 = 234/12 = 19.5 > 19

    Some group must sum to 20 or more to pull the average above 19.

Theory

The average of a bunch of numbers is at most the maximum of the bunch. For example if the bunch is b1,b2,b3:

avg = (b1 + b2 + b3) / 3 ≤ (max + max + max) / 3 = max
therefore
avg ≤ max

If moreover the maximum is an integer (usually because the whole bunch are integers), and if the average is strictly greater than an integer L, then the maximum is L+1 or more. For example, if avg = 1.11, then 1.11 ≤ max, this forces max to be 2 or more if max is an integer.

In the solved examples, I say “some member is L+1 or more to pull the average above L” hoping that students understand more readily. (Most students are familiar with the phenomenon of some nerd pulling up the class average, making the life of everyone else harder!) It is the same as saying “the maximum member is L+1 or more”.

Credit and Reference

I learned it from Dijkstra's the undeserved status of the pigeon-hole principle (HTML, PDF of handwriting).

I have more Math Homework Help