MATC44H3 Chap.2 The Pigeonhole Principle and Its Strong Form
The Pigeonhole Principle and Its Strong Form
The statement and its proof
If n objects are placed into m boxes and n is greater than m, some box contains at least two objects. The lecture proves this by contradiction: if every box held at most one object, there could be at most m objects in total. The principle is not constructive.
It promises a crowded box without identifying it, and the lecture also gives a function form: a function from a larger finite set to a smaller one sends two different inputs to the same output.
Stronger guarantees
Three refinements appear in the slides. The strong form says that mk + 1 objects in m boxes force some box to hold at least k + 1, and that this number is sharp.
A generalized version from the Morris textbook says n items in m categories with n greater than km force k + 1 into one category. A further version allows a different target for each category, which is exactly what problems with limited stock of each colour require.
The ceiling form
The ceiling of x is the least integer at least x. If N objects go into k boxes, some box holds at least the ceiling of N/k.
The proof uses the inequality that a ceiling is less than x + 1, and the bound is sharp because an even spread achieves it exactly.
Lecture examples apply it to the students on a campus and the residents of a city.
What to practise
Population questions, minimum-draw questions with limited stock, and proofs of the principle itself are the three shapes this chapter prepares for, each written with the pigeons, the holes and the sharpness example stated.
What this chapter covers
- 01
Pigeonhole statement and proof by contradiction
- 02
The function form of the principle
- 03
Strong form with mk + 1 objects
- 04
Generalized and uneven-target versions
- 05
The ceiling function and the ceiling form
- 06
Sharpness of the bound
- 07
Capped categories and minimum draws
Worked example · free
Minimum draws for five of one colour
- 2Worst case: 4 black, 4 white and all 3 grey, which is 11 marbles with no colour at five.
- 2Grey cannot reach five, so a twelfth marble must be black or white and makes five of that colour.
Key terms
- Strong Form
- The strong form of the pigeonhole principle says mk + 1 objects in m boxes put at least k + 1 in some box.
- Function Form
- The function form says a function from a larger finite set to a smaller one maps two different inputs to the same output.
- Nonconstructive Proof
- A nonconstructive proof shows an object exists without identifying it.
- Pigeonhole
- A pigeonhole is one of the categories into which the objects of a pigeonhole argument are sorted.
- Average Argument
- An average argument notes that some box must hold at least the average number of objects per box.
The Pigeonhole Principle and Its Strong Form FAQ
What does it mean that the pigeonhole principle is not constructive?
It tells you a box with two objects exists but not which box. That makes it ideal for existence questions and useless on its own for construction questions. If a problem asks you to exhibit the two objects, you need a different argument or an explicit search.
When should I use the ceiling form instead of the basic form?
Use the basic form when you need two objects in one box. Use the ceiling form whenever the target is three, four or more, or whenever the question gives large numbers such as a population and a list of possible values. Divide the objects by the boxes and round up.
Why is the strong form called sharp?
Because mk objects can be spread with exactly k in each of the m boxes, so no box reaches k + 1. One more object, mk + 1, forces k + 1 somewhere. The number of objects cannot be lowered without losing the guarantee.
How do I handle colours with too few items to reach the target?
Use the version with a different target for each category, or reason through the worst case. Fill each colour up to one below the target or to its full stock if that is smaller, add the counts, and add one. The extra item must land in a colour that can still reach the target.
Exam move
Prove the basic and ceiling forms from memory, since both are short and both can be asked. Then work one minimum-draw question with capped colours and one population question with a ceiling, writing the pigeons, the holes and the sharpness example every time. Check each answer by building the worst case explicitly.
Working through The Pigeonhole Principle and Its Strong Form in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 The Pigeonhole Principle and Its Strong Form question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
