HSC Study

The Pigeonhole Principle

The pigeonhole principle and its generalisation, a proof by contradiction, and how to choose pigeonholes to prove results about numbers, points and people.

35 min · Combinatorics

The full teaching. Start here.

The short version

  • Pigeonhole principle: pigeons in holes means some hole has at least .
  • Generalised: pigeons in holes means some hole has at least , so at least the next whole number up.
  • Proof: by contradiction. If every hole had fewer, the total would be too small.
  • Minimum number to guarantee something: imagine the worst case, then add one.
  • Proofs: state clearly what the pigeons are and what the holes are. Choose holes so that two pigeons in one hole gives the result you want.

The principle

If people are in a room, two share a birth month: there are only months to go round. This obvious-sounding fact is surprisingly powerful.

Pigeonhole principle

If or more objects (pigeons) are placed into boxes (pigeonholes), then at least one box contains at least objects.

It is an existence result. It says some hole is crowded, not which one.

CheckpointAnswer before reading on.

Why must two people in any group of 13 have birthdays in the same month?

Select one answer

Hint 1Months are pigeonholes.

Hint 213 people, 12 months.

Hint 3n + 1 into n.

CheckpointAnswer before reading on.

Twelve people are in a room. Can you guarantee that two share a birth month?

Select one answer

Hint 1Count pigeons and holes.

Hint 212 into 12.

Hint 3One each is possible.

CheckpointAnswer before reading on.

What does the pigeonhole principle tell you?

Select one answer

Hint 1Existence.

Hint 2Not which hole.

Hint 3Some hole.

CheckpointAnswer before reading on.

How many integers must be chosen to guarantee that two leave the same remainder when divided by 7?

Hint 1Remainders 0 to 6.

Hint 27 holes.

Hint 38.

CheckpointAnswer before reading on.

How many people are needed to guarantee that two have the same first and last initials (26 letters)?

Hint 1 pairs.

Hint 2676 holes.

Hint 3677.

Proving it

Worked example3 marks

Proof of the pigeonhole principle

Prove that if pigeons are placed in pigeonholes, some pigeonhole contains at least pigeons. Deduce the case of pigeons in holes.

Assume the opposite

Proof by contradiction.

Suppose every pigeonhole contains fewer than pigeons.

Add up

Count all the pigeons.

Adding over all holes, the total number of pigeons is less than .

Contradiction

There are exactly n pigeons.

This contradicts there being pigeons. So some hole contains at least .

Special case

n + 1 pigeons, n holes.

Some hole contains at least pigeons. Since the count is a whole number, that is at least .

Answer

Some hole holds at least pigeons, and so at least the smallest integer . With pigeons in holes, that means at least .

Is that answer sensible?

pigeons in holes: the principle says some hole has at least , so at least . The most even split, , confirms that is achieved and cannot be avoided.

Exam question

Standard · about 3 min

2 marks

Prove that if pigeons are placed into pigeonholes, some pigeonhole contains at least pigeons. (2 marks)

Hint 1Contradiction.

Hint 2Suppose each hole has at most 1.

Hint 3Total at most .

Where students lose marks on this one
  • Giving an example.

    Why it happens: Illustrating instead of proving.

    Prove for general n.

Written for this site.

Exam question

Harder · about 3 min

2 marks

Prove that if pigeons are placed in pigeonholes, then some pigeonhole contains at least pigeons. (2 marks)

Hint 1Contradiction.

Hint 2Each hole fewer than .

Hint 3Total fewer than .

Where students lose marks on this one
  • Assuming each hole has at most n/k.

    Why it happens: Negating wrongly.

    The negation of "at least n/k" is "fewer than n/k".

Written for this site.

Using the generalised form

Because pigeon counts are whole numbers, "at least " means at least rounded up. To find the fewest pigeons that guarantee in some hole, imagine the worst case of in every hole, which uses pigeons, and add one: .

CheckpointAnswer before reading on.

Fifty pigeons sit in 7 pigeonholes. What is the largest number that some pigeonhole is guaranteed to hold at least?

Hint 1At least .

Hint 2.

Hint 3Round up to an integer.

CheckpointAnswer before reading on.

In a school of 100 students, at least how many must share a birth month?

Select one answer

Hint 1.

Hint 2.

Hint 3Round up.

CheckpointAnswer before reading on.

Twenty-five pigeons are placed into 6 holes. Some hole must contain at least:

Select one answer

Hint 1.

Hint 2.

Hint 35.

CheckpointAnswer before reading on.

What is the smallest number of people needed to guarantee that three share a birth month?

Hint 1Worst case: two per month.

Hint 2.

Hint 3Add one.

CheckpointAnswer before reading on.

Thirty students each score a whole number from 0 to 10 on a quiz. At least how many students must have the same score?

Hint 111 possible scores.

Hint 2.

Hint 3Round up.

Worst-case reasoning

"How many must you take to be sure?" questions are pigeonhole arguments in disguise. Picture an unlucky draw that avoids the goal for as long as possible, then take one more.

CheckpointAnswer before reading on.

A drawer holds red, blue and black socks (many of each). In the dark, how many socks must you take to be sure of a matching pair?

Hint 1Colours are holes.

Hint 23 holes.

Hint 33 + 1.

CheckpointAnswer before reading on.

A drawer holds 10 red and 10 blue socks. How many must you take (in the dark) to be sure of getting two red socks?

Hint 1Worst case: all the blues first.

Hint 210 blue + 2 red.

Hint 312.

CheckpointAnswer before reading on.

How many cards must be drawn from a standard deck to guarantee three of the same suit?

Hint 14 suits.

Hint 2Worst case: 2 of each.

Hint 38 + 1.

CheckpointAnswer before reading on.

How many cards must be drawn from a standard deck to guarantee four hearts?

Hint 1Worst case: all non-hearts first.

Hint 239 non-hearts.

Hint 339 + 4.

Common mistake

To be sure of three cards of the same suit, draw 3 × 4 = 12.

Why it happens: Counting a full set in every suit instead of the worst case.

The worst case avoids three of a suit for as long as possible: two of each suit, cards. The next card must make three: . The pattern is , not .

Choosing the pigeonholes

In a proof, the skill is in the choice of holes. Design them so that two pigeons in the same hole gives exactly what you are asked to prove.

side 1, four squares of side ½side 2, four triangles of side 1
Left: five points in a unit square, split into four squares of side ½. Two points must share a small square, so they are at most its diagonal, √2⁄2, apart. Right: the same idea in an equilateral triangle of side 2, split into four triangles of side 1.

Worked example3 marks

Choosing pigeonholes in a proof

Prove that if any numbers are chosen from , two of the chosen numbers are consecutive.

Choose the holes

Sharing a hole must mean consecutive.

Split into the pairs .

Count

Pigeons are the chosen numbers.

There are chosen numbers and pairs.

Apply the principle

n + 1 into n.

Some pair contains two chosen numbers. The two numbers in a pair are consecutive.

Answer

Two of the chosen numbers lie in the same pair , so they are consecutive.

Is that answer sensible?

The bound is sharp: choosing the odd numbers gives no consecutive pair. So is the least number that works.

CheckpointAnswer before reading on.

To show that any numbers chosen from include two that add to , what should the pigeonholes be?

Select one answer

Hint 1Pairs that add to 11.

Hint 2

Hint 35 holes.

Exam question

Standard · about 3 min

2 marks

Prove that any numbers chosen from include two whose sum is . (2 marks)

Hint 1Pair up numbers adding to 11.

Hint 25 pairs.

Hint 36 into 5.

Where students lose marks on this one
  • Not stating the holes.

    Why it happens: Using the principle without naming holes.

    Always state pigeons and holes.

Written for this site.

Exam question

Standard · about 3 min

2 marks

Prove that any numbers chosen from include two consecutive numbers. (2 marks)

Hint 1Pairs {1, 2}, {3, 4}, …

Hint 250 pairs.

Hint 351 into 50.

Where students lose marks on this one
  • Using 100 holes.

    Why it happens: Wrong holes.

    Holes must force the conclusion.

Written for this site.

Exam question

Straightforward · about 2 min

2 marks

Prove that among any integers, two have an even sum. (2 marks)

Hint 1Odd and even.

Hint 22 holes, 3 integers.

Hint 3Same parity sum is even.

Where students lose marks on this one
  • Only considering odd + odd.

    Why it happens: Missing a case.

    Both same-parity cases give even sums.

Written for this site.

Exam question

Standard · about 3 min

2 marks

Prove that among any integers, two have a difference divisible by . (2 marks)

Hint 1Remainders on division by 4.

Hint 24 holes.

Hint 3Same remainder: difference divisible by 4.

Where students lose marks on this one
  • Stopping at "two share a remainder".

    Why it happens: Not finishing the argument.

    Show why the difference is divisible.

Written for this site.

Exam question

Harder · about 4 min

3 marks

Five points are placed inside a square of side . Prove that two of them are at most apart. (3 marks)

Hint 1Split into four squares of side .

Hint 2Five points, four squares.

Hint 3Diagonal of a small square.

Where students lose marks on this one
  • Dividing into 5 regions.

    Why it happens: Choosing too many holes.

    You need fewer holes than points.

Written for this site.

Exam question

Harder · about 3 min

2 marks

Five points are placed inside an equilateral triangle of side . Prove that two of them are at most unit apart. (2 marks)

Hint 1Join the midpoints of the sides.

Hint 2Four triangles of side 1.

Hint 3Largest distance in a small triangle is 1.

Where students lose marks on this one
  • Using three regions.

    Why it happens: Poor choice of holes.

    Midpoints give four congruent triangles.

Written for this site.

Exam question

Hardest asked · about 5 min

3 marks

At a party of people, some pairs shake hands. Prove that two people shook the same number of hands. (3 marks)

Hint 1Possible counts .

Hint 2 and cannot both occur.

Hint 3So only values.

Where students lose marks on this one
  • Using n holes.

    Why it happens: Missing the key observation.

    0 and n − 1 are mutually exclusive.

Written for this site.

What lifts this to a Band 6

Write the words "pigeons" and "pigeonholes" in your answer: "The pigeons are the integers; the pigeonholes are the possible remainders on division by ." Markers look for exactly this. Then finish the argument: explain why two pigeons in the same hole give the result, rather than stopping at "so two share a hole".

Friends and strangers

Among any people, there are always who all know each other or who are all strangers. Pick one person, . Of the other , by the pigeonhole principle at least are in the same category relative to : say knows , and . If any two of know each other, they form a trio of friends with . If not, are three mutual strangers. With people this can fail, so is the smallest number that works. This is the first case of Ramsey theory, which studies how complete disorder is impossible in large enough structures.