MATC44H3 Chap.3 Choosing Pigeonholes and Proving Sharp Bounds
Choosing Pigeonholes and Proving Sharp Bounds
The design is the difficulty
After the principle itself, pigeonhole questions in this course differ only in how the holes are designed. The practice set uses complementary pairs for sums, blocks of two for consecutive numbers, blocks of four chairs in a row, equal rectangles or squares for points in a region, the possible last digits of a square, and classes of two-digit numbers with the same digit sum.
The lecture adds pairs built so that a sum or a difference is divisible by 100.
Counting holes exactly
The answer depends on the number of holes, so singleton holes matter. Numbers that have no partner, such as the middle value of a range or the values whose complement is themselves, form holes of their own, and each such hole can hold only one distinct chosen number.
A design is correct when sharing a hole really delivers the property and every element lands in exactly one hole.
The second half of the answer
Questions asking for the smallest number that guarantees a property, or for all values of k that guarantee it, require a counterexample one below the answer.
The course solutions supply it every time: a choice of numbers below the midpoint, points near the corners of a square, or people seated in a repeating pattern that leaves every fourth chair empty. The first assignment applies the same thinking to subsets of consecutive integers.
What this chapter covers
- 01
Complementary pairs and singleton holes
- 02
Blocks of consecutive numbers and chairs
- 03
Cutting a square into equal cells
- 04
Units digits of squares as holes
- 05
Digit-sum classes and small classes set aside
- 06
Counting memberships when objects are sets
- 07
Counterexamples one below the answer
Worked example · free
Consecutive numbers among chosen ones
- 2Holes {1, 2}, {3, 4}, … , {29, 30}: fifteen pairs of consecutive numbers covering the set.
- 2Sixteen chosen numbers put two in one pair, and those two are consecutive.
- 2Fifteen is not enough: the odd numbers 1, 3, … , 29 contain no two consecutive numbers.
Key terms
- Complementary Pair
- A complementary pair is two numbers whose sum equals a fixed target, used as one pigeonhole.
- Singleton Hole
- A singleton hole is a pigeonhole containing only one possible value, such as the middle number of a range.
- Extremal Example
- An extremal example is a largest possible selection that avoids the property, proving a bound cannot be lowered.
- Incidence Count
- An incidence count totals the pairs of an element and a set containing it, to apply the pigeonhole principle to memberships.
- Digit Sum
- The digit sum of a whole number adds up its decimal digits, so 52 has digit sum 7.
Choosing Pigeonholes and Proving Sharp Bounds FAQ
Why do singleton holes change the answer?
Each singleton can hold only one of the chosen distinct numbers, so it absorbs a choice without creating a pair. If you forget it, your hole count is one short and your guarantee is one too small. Write all the holes, including the unpaired values, before applying the principle.
How do I show a pigeonhole bound is the best possible?
Exhibit a selection of one fewer object that avoids the property and explain why it does. For sums, choose all the numbers on one side of the midpoint. For points in a square, place them at well-separated lattice points or near the corners. The example must be concrete and checkable.
What are the holes when the question is about units digits of squares?
A perfect square can only end in 0, 1, 4, 5, 6 or 9, so those six digits are the holes. Placing each chosen integer according to the last digit of its square puts integers with equal last digits together, and their squares then differ by a multiple of 10.
How do pigeonhole arguments work with points in a square?
Cut the square into equal smaller pieces and treat each piece as a hole. Two points in one piece are no farther apart than the piece's diagonal, which the Pythagorean theorem gives. The number of pieces decides how many points force two, or three, into the same piece.
Exam move
For each hole design in the chapter table, invent one new question with different numbers, solve it, and write the counterexample half. Then time yourself on two practice-set questions, checking the hole count twice before writing the conclusion.
Working through Choosing Pigeonholes and Proving Sharp Bounds in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Choosing Pigeonholes and Proving Sharp Bounds 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.
