HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Notes
  2. /The Pigeonhole Principle: Quick Revision
Mathematics

The Pigeonhole Principle: Quick Revision

A brief note on the pigeonhole principle: the simple and generalised forms, forcing r objects into a box, averages, monotone runs, remainders, prefix sums, odd parts and points in a figure. With practice, a program and questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on The Pigeonhole Principle. Read it before a test. Try each question at the end before you open its answer.

The principle

  • Simple form: n+1n + 1n+1 objects in nnn boxes put at least two objects in some box.
  • Generalised form: NNN objects in kkk boxes put at least ⌈Nk⌉\left\lceil \dfrac{N}{k} \right\rceil⌈kN​⌉ in some box.
  • Forcing rrr: with kkk boxes, k(r−1)+1k(r - 1) + 1k(r−1)+1 objects make sure of rrr in one box.
  • Averages: some number of a list is at least the average.
  • A fewest-number answer needs two parts: a proof that it is enough and an example that one fewer fails.

Choosing the boxes

  • Remainders: m+1m + 1m+1 whole numbers include two with a difference divisible by mmm.
  • Pairs: put rrr and m−rm - rm−r together for "a sum or a difference".
  • Prefix sums: S0=0,S1,…,SmS_0 = 0, S_1, \dots, S_mS0​=0,S1​,…,Sm​ give a block of neighbours with a sum divisible by mmm.
  • Odd parts: n+1n + 1n+1 numbers from 111 to 2n2n2n include one that divides another.
  • Pieces of a figure: two points in one piece are at most the width of the piece apart.
  • Erdős and Szekeres: n2+1n^2 + 1n2+1 different numbers have a monotone run of length n+1n + 1n+1.

A worked example

Show that among any 666 whole numbers, two have a difference divisible by 555.

  1. Objects and boxes. The six numbers, and the five remainders 000 to 444.
  2. The principle. Two numbers share a remainder.
  3. Conclusion. Their difference is divisible by 555.

Practice with new numbers

A program to try

The program checks two pigeonhole answers by trying every case.

Read it first. Then run it. Does the first answer match the pairs {1,12},{2,11},…\{1, 12\}, \{2, 11\}, \dots{1,12},{2,11},…?

1. Change 13 to 11 in the first part, two times. Predict the new answer first.

Mistakes to avoid

  • Rounding down where the ceiling is needed.
  • Using krkrkr in place of k(r−1)+1k(r - 1) + 1k(r−1)+1.
  • Forgetting S0=0S_0 = 0S0​=0 in a prefix-sum argument.
  • Boxes that overlap or miss some objects.
  • No example for "one fewer is not enough".

Check yourself

  1. How many people make sure that two share a birth month?
  1. 333333 pencils go into 444 cups. At least how many pencils are in the fullest cup?
  1. How many whole numbers make sure that two have a difference divisible by 999?
  1. Five points lie in a square of side 444 cm. How close must two of them be?
  1. Give a list of 444 different numbers with no run of 333 going up or going down.

Sources

  • R. A. Brualdi, Introductory Combinatorics, Chapter 3.
  • A. Engel, Problem-Solving Strategies, Chapter 4.
← All Notes
← Convexity and Inequality Techniques: Quick RevisionRecurrences and Counting by Recursion: Quick Revision →
More onPigeonhole Principle, Recursion and Graph Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. The principle
  2. Choosing the boxes
  3. A worked example
  4. Practice with new numbers
  5. A program to try
  6. Mistakes to avoid
  7. Check yourself
  8. Sources

Goes with the lesson

  1. Pigeonholes in numbers and geometryThe Pigeonhole Principle

More notes on this topic

  1. Graph Theory: Quick Revision
  2. Recurrences and Counting by Recursion: Quick Revision
All notes on this topic →