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
The Pigeonhole Principle
  1. 1The pigeonhole principle
  2. 2The generalised pigeonhole principle
  3. 3Pigeonholes in numbers and geometry
  1. Mathematics
  2. /The Pigeonhole Principle
  3. /The generalised pigeonhole principle

Course 30.1·Lesson 2 of 3

The generalised pigeonhole principle

If NNN objects go into kkk boxes, some box holds at least ⌈N/k⌉\lceil N/k \rceil⌈N/k⌉ objects, where ⌈x⌉\lceil x \rceil⌈x⌉ means xxx rounded up to a whole number. To force rrr

about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Lesson 2 of 3Show all lessonsHide
The Pigeonhole Principle
  1. 1The pigeonhole principle
  2. 2The generalised pigeonhole principle
  3. 3Pigeonholes in numbers and geometry

Try the code and the simulations beside the lesson.

What you will be able to do

  • use the generalised pigeonhole principle with the ceiling function;
  • find the fewest objects that force rrr objects into one box;
  • use the averaging form, and prove the Erdős–Szekeres theorem.

More than two in a box

A school has 404040 students and 121212 months. Two share a birth month, of course. But can we say more? If every month had at most 333 students, the school would have at most 363636 students. It has 404040. So some month has at least 444 students.

The generalised pigeonhole principle. If NNN objects are placed in kkk boxes, some box holds at least ⌈Nk⌉\left\lceil \dfrac{N}{k} \right\rceil⌈kN​⌉ objects.

The symbol ⌈x⌉\lceil x \rceil⌈x⌉ is the ceiling of xxx: the smallest whole number that is at least xxx. So ⌈3.25⌉=4\lceil 3.25 \rceil = 4⌈3.25⌉=4 and ⌈3⌉=3\lceil 3 \rceil = 3⌈3⌉=3. In the example, ⌈4012⌉=4\left\lceil \dfrac{40}{12} \right\rceil = 4⌈1240​⌉=4.

Proof. If every box held fewer than Nk\dfrac{N}{k}kN​ objects, the total would be less than k×Nk=Nk \times \dfrac{N}{k} = Nk×kN​=N. That is impossible, so some box holds at least Nk\dfrac{N}{k}kN​. A box holds a whole number, so it holds at least ⌈Nk⌉\left\lceil \dfrac{N}{k} \right\rceil⌈kN​⌉.

Forcing r in one box

Turn the question round. How many objects make sure that some box of kkk holds rrr?

The worst case puts r−1r - 1r−1 objects in every box. That uses k(r−1)k(r - 1)k(r−1) objects and no box reaches rrr. The next object must go somewhere, and that box reaches rrr. So the answer is

k(r−1)+1.\displaystyle k(r - 1) + 1.k(r−1)+1.

For r=2r = 2r=2 this is k+1k + 1k+1, the first principle again.

The averaging form

The same reasoning works for numbers that are not counts.

Averaging principle. Among some real numbers, at least one is at least their average, and at least one is at most their average.

Example: the numbers 111 to 101010 are written round a circle in any order. Show that some three neighbours add up to at least 171717.

  1. The ten blocks. There are 101010 blocks of three neighbours.
  2. Add all the blocks. Each number lies in exactly three blocks, so the sum of all the block sums is 3×55=1653 \times 55 = 1653×55=165.
  3. Average. The average block sum is 16.516.516.5. Some block is at least 16.516.516.5, and a block sum is a whole number, so it is at least 171717.

The Erdős–Szekeres theorem

Look at the list 3, 1, 4, 5, 9, 2, 6. The terms 1,4,5,91, 4, 5, 91,4,5,9 go up, in their order in the list. We call that an increasing run of length 444 (books call it an increasing subsequence). A decreasing run goes down, such as 9,29, 29,2.

Theorem (Erdős and Szekeres, 1935). Any list of n2+1n^2 + 1n2+1 different real numbers has an increasing run of length n+1n + 1n+1 or a decreasing run of length n+1n + 1n+1.

Proof.

  1. Labels. Give each term the pair (a,d)(a, d)(a,d). Here aaa is the length of the longest increasing run that ends at that term, and ddd is the length of the longest decreasing run that ends there.
  2. All labels differ. Take two terms, xxx before yyy. If x<yx < yx<y, add yyy to the best increasing run ending at xxx: the aaa of yyy is bigger. If x>yx > yx>y, the ddd of yyy is bigger in the same way.
  3. Pigeonholes. Suppose every run has length at most nnn. Then aaa and ddd take values 111 to nnn, so there are only n2n^2n2 possible labels. But there are n2+1n^2 + 1n2+1 terms with different labels. This is a contradiction.

The number n2+1n^2 + 1n2+1 cannot be lowered. The list 3, 2, 1, 6, 5, 4, 9, 8, 7 has 9=329 = 3^29=32 terms and no run of length 444 either way.

The list 3, 1, 4, 5, 9, 2, 6 drawn as seven dots, with the position in the list across and the value up. The dots 1, 4, 5, 9 are joined by a green line that climbs, an increasing run of length 4. Under each dot its label (a, d) is written: (1, 1), (1, 2), (2, 1), (3, 1), (4, 1), (2, 2), (4, 2). All seven labels are different.

Practise with new numbers

Try it in Python

The program gives every term of a list its label (a,d)(a, d)(a,d), as in the proof, and prints them. No two labels are the same.

Read it first. Then run it. Look for two terms with the same label.

1. Replace the list with [3, 2, 1, 6, 5, 4, 9, 8, 7]. What is the largest label now?

2. Add 10 at the end of that list. Which run of length 444 appears?

Common mistakes

  • Rounding down. 4012=3.33\dfrac{40}{12} = 3.331240​=3.33, so some box holds at least 444, not 333. The ceiling rounds up.
  • Using krkrkr for "force rrr". The worst case is r−1r - 1r−1 in every box, so the answer is k(r−1)+1k(r - 1) + 1k(r−1)+1.
  • A run that is not in order. The terms of a run keep their order in the list. You may skip terms but not move them.
  • Equal numbers. The theorem is for different numbers. With repeats, use "not decreasing" runs instead.

Remember these

  • NNN objects in kkk boxes: some box holds at least ⌈Nk⌉\left\lceil \dfrac{N}{k} \right\rceil⌈kN​⌉.
  • To force rrr in a box of kkk: k(r−1)+1k(r - 1) + 1k(r−1)+1 objects.
  • Some number is at least the average of a list.
  • n2+1n^2 + 1n2+1 different numbers contain a monotone run of length n+1n + 1n+1.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. A library puts 757575 books on 888 shelves. At least how many books must the fullest shelf hold?
  1. A bag holds many beads of 444 colours. What is the fewest you must take to be sure of 555 beads of one colour?
  1. Seven numbers have the average 121212. Must one of them be at least 121212?
  1. Find an increasing run of length 333 or a decreasing run of length 333 in the list 4, 7, 2, 6, 1, 5.
  1. Why does the list 2,1,4,32, 1, 4, 32,1,4,3 not break the Erdős–Szekeres theorem for n=2n = 2n=2?

References

  • R. A. Brualdi, Introductory Combinatorics, Chapter 3, the strong form of the pigeonhole principle.
  • P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935).

Enroll free in The Pigeonhole Principle

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (3)

A class of 50 students takes a quiz marked out of 10…Hard · High School (11–12) · by StemPy Lab
Ten students of different heights stand in a line in some order…Advanced · High School (11–12) · by StemPy Lab
The numbers 1, 2, …, 12 are written round a circle in any order, like a clock face that has been…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 3Pigeonholes in numbers and geometry
← The Pigeonhole Principle
← The pigeonhole principlePigeonholes in numbers and geometry →

Discussion (0)

Log in to join the discussion.

Loading…

objects into one box you need
k(r−1)+1k(r - 1) + 1k(r−1)+1
objects. The same idea, used on averages, says that some value is at least the average. It proves the theorem of Erdős and Szekeres on increasing and decreasing runs.