If N objects go into k boxes, some box holds at least ⌈N/k⌉ objects, where ⌈x⌉ means x rounded up to a whole number. To force r
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
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 r objects into one box;
use the averaging form, and prove the Erdős–Szekeres theorem.
More than two in a box
A school has 40 students and 12 months. Two share a birth month, of course. But can we say more? If every month had at most 3 students, the school would have at most 36 students. It has 40. So some month has at least 4 students.
The generalised pigeonhole principle. If N objects are placed in k boxes, some box holds at least ⌈kN⌉ objects.
The symbol ⌈x⌉ is the ceiling of x: the smallest whole number that is at least x. So ⌈3.25⌉=4 and ⌈3⌉=3. In the example, ⌈1240⌉=4.
Proof. If every box held fewer than kN objects, the total would be less than k×kN=N. That is impossible, so some box holds at least kN. A box holds a whole number, so it holds at least ⌈kN⌉.
Forcing r in one box
Turn the question round. How many objects make sure that some box of k holds r?
The worst case puts r−1 objects in every box. That uses k(r−1) objects and no box reaches r. The next object must go somewhere, and that box reaches r. So the answer is
k(r−1)+1.
For r=2 this is k+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 1 to 10 are written round a circle in any order. Show that some three neighbours add up to at least 17.
The ten blocks. There are 10 blocks of three neighbours.
Add all the blocks. Each number lies in exactly three blocks, so the sum of all the block sums is 3×55=165.
Average. The average block sum is 16.5. Some block is at least 16.5, and a block sum is a whole number, so it is at least 17.
The Erdős–Szekeres theorem
Look at the list 3, 1, 4, 5, 9, 2, 6. The terms 1,4,5,9 go up, in their order in the list. We call that an increasing run of length 4 (books call it an increasing subsequence). A decreasing run goes down, such as 9,2.
Theorem (Erdős and Szekeres, 1935). Any list of n2+1 different real numbers has an increasing run of length n+1 or a decreasing run of length n+1.
Proof.
Labels. Give each term the pair (a,d). Here a is the length of the longest increasing run that ends at that term, and d is the length of the longest decreasing run that ends there.
All labels differ. Take two terms, x before y. If x<y, add y to the best increasing run ending at x: the a of y is bigger. If x>y, the d of y is bigger in the same way.
Pigeonholes. Suppose every run has length at most n. Then a and d take values 1 to n, so there are only n2 possible labels. But there are n2+1 terms with different labels. This is a contradiction.
The number n2+1 cannot be lowered. The list 3, 2, 1, 6, 5, 4, 9, 8, 7 has 9=32 terms and no run of length 4 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), as in the proof, and prints them. No two labels are the same.
Common mistakes
Rounding down.1240=3.33, so some box holds at least 4, not 3. The ceiling rounds up.
Using kr for "force r". The worst case is r−1 in every box, so the answer is k(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
N objects in k boxes: some box holds at least ⌈kN⌉.
To force r in a box of k: k(r−1)+1 objects.
Some number is at least the average of a list.
n2+1 different numbers contain a monotone run of length n+1.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
A library puts 75 books on 8 shelves. At least how many books must the fullest shelf hold?
A bag holds many beads of 4 colours. What is the fewest you must take to be sure of 5 beads of one colour?
Seven numbers have the average 12. Must one of them be at least 12?
Find an increasing run of length 3 or a decreasing run of length 3 in the list 4, 7, 2, 6, 1, 5.
Why does the list 2,1,4,3 not break the Erdős–Szekeres theorem for n=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.
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.