Motivation
A counting argument can establish existence without telling us the total number of possible arrangements. If thirteen students choose among twelve months, two must choose the same month. We do not need to enumerate their choices. We only need to compare the number of students with the capacity of the proposed arrangement in which every month is chosen at most once.
The difficulty in a useful pigeonhole argument is usually deciding what the boxes should be. For divisibility, they will be remainders of partial sums. For an ordered sequence, they will be pairs of lengths of subsequences ending at a particular position. These choices record information that can be extended when a new object is considered. A collision between records then produces the desired mathematical object.
We will also ask whether a guarantee is sharp. A proof that some configuration must exist above a threshold should be accompanied, when possible, by an arrangement just below that threshold in which it does not exist. Such examples explain exactly what the theorem promises.
Definitions
Definition 2.6.1
(Objects, boxes and occupancy)
Let be a finite set of labeled objects, and let be an integer. An assignment to boxes is a function . Box has occupancy . The fibers partition , so
Empty boxes are allowed. The ceiling is the least integer greater than or equal to the real number .
The boxes need not be physical containers. A box may be a remainder class, an interval, a color, or a possible pair of integer labels. To apply the sum identity, every object must belong to exactly one box. A family of overlapping regions is not automatically a partition: specify a boundary convention or a definite assignment rule.
Definition 2.6.2
(Consecutive blocks and subsequences)
For a sequence , a nonempty consecutive block has positions with . A subsequence has positions ; its entries need not be adjacent. It is strictly increasing if , and strictly decreasing if every inequality is reversed. A one-entry subsequence satisfies both definitions.
A guarantee is sharp at a given integer threshold if it holds at that threshold but can fail one below it. This describes a worst-case guarantee; some shorter sequences or smaller assignments may already contain the required configuration.
Theorem/Proposition
Theorem 2.6.3
(Sharp generalized pigeonhole principle)
For objects in boxes, at least one box contains at least objects. This bound is best possible for every pair .
More generally, let be nonnegative integer capacities. If , then some box has .
The second statement allows the forbidden occupancies to depend on the box. To force some box to reach a specified positive integer threshold , it suffices to have more than objects. Equality does not suffice: put exactly objects in each box.
Theorem 2.6.4
(A divisible consecutive sum)
Let be an integer. For any integers , some nonempty consecutive block has sum divisible by .
The integers may be zero or negative. Divisibility means the sum equals for some integer ; the sum need not be positive or nonzero.
Theorem 2.6.5
(Sharp monotone-subsequence guarantee)
Let be integers. Every sequence of pairwise distinct real numbers has a strictly increasing subsequence of length or a strictly decreasing subsequence of length . For each , there is a sequence of length with neither type.
The conclusion is an inclusive alternative: both kinds of subsequence may occur. It does not assert that there are many of them, that they are consecutive, or that the entire original sequence is monotone.
Proof sketch or proof idea
Convert failure into a capacity bound
Proof
(Largest occupancy, a balanced assignment and unequal capacities)
Let be the largest occupancy. Since for every , the sum identity gives . Thus . Because is an integer, . This also covers , when every box is empty.
To prove sharpness, divide by : write with integers and . Put objects in each of boxes and in each of the remaining boxes. If , the maximum is ; otherwise it is . In either case it equals . The construction also works when , since then .
For unequal capacities, suppose instead that for every . Summing gives , contradicting the stated strict inequality. The proof explains why exceeding the total capacity, rather than merely reaching it, is essential.
Record prefixes so that subtraction produces a block
Proof
(Two prefixes with equal remainders)
Define the prefix sums
There are indexed prefixes, including the empty one. Assign prefix index to the unique remainder of in modulo . These are boxes, even when some sums are negative. The pigeonhole principle gives two distinct indices with the same remainder. Order them as . Then
The inequality makes the block nonempty. Subtracting prefixes makes it consecutive. Those are two separate parts of the conclusion, and both come from the choice of objects, not from pigeonhole alone. When , the two prefixes give the only one-entry block, whose integer sum is divisible by .
Label what can end at each position
For a sequence of length , let be the greatest length of a strictly increasing subsequence ending at position , and let be the corresponding greatest decreasing length. The maxima exist: there are finitely many subsequences ending at , and the one-entry subsequence is available. In particular .
Proof
(Distinct endpoint pairs in an rectangle)
Take two positions . If , append to an increasing subsequence ending at . Its indices remain increasing, so . If , the same argument with a decreasing subsequence gives .
Pairwise distinctness ensures that one of these two cases always occurs. Therefore : at least one coordinate has strictly increased, although the other coordinate need not increase.
Now suppose the two desired types of subsequence are both absent. Then every endpoint pair lies in
which has elements. But all endpoint pairs are different. This would assign objects to boxes without a collision, contradicting the pigeonhole principle. Hence at least one desired subsequence exists.
Proof X-ray
Where distinctness and the count rs+1 are used
The proof separates three tasks. The first is a record carried by every position: the pair is defined because the one-entry subsequence makes both maxima at least . The second is injectivity of , and it is the only step that uses pairwise distinctness. For the comparison of with must come out strictly one way or the other, and each outcome raises a specified coordinate. If is allowed, neither append is legal and the records may coincide: in every pair is .
The third task turns the negated conclusion into a range. If some were at least , the last terms of a longest increasing subsequence ending at would already be the forbidden object; so the absence of an increasing subsequence of length says exactly that for every , and similarly . The count enters only here, through the weakest form of the pigeonhole principle: a set of positions has no injection into a set of pairs. The argument closes by contradiction and does not say which alternative holds; the recurrence described after the extremal example recovers an explicit witness.
Notice what the proof does not claim: the endpoint pairs need not be ordered coordinate by coordinate. A later position can have a smaller increasing label and a larger decreasing label. Only distinctness of the pairs is needed.
Build the extremal example
Proof
(Concatenated descending blocks)
For sharpness, concatenate blocks, each of length . Block , for , is
Entries decrease within a block, but every entry of a later block is larger than every entry of an earlier block. An increasing subsequence can therefore take at most one entry from each block, so has length at most . A decreasing subsequence cannot cross from an earlier block to a later one, so is contained in a single block and has length at most . These two restrictions prove the required absence at length . They also handle or .
The endpoint proof gives a finite procedure for finding a witness. For each position , examine all earlier positions. Set to one plus the largest for which and , using zero when there is no such . Define with in the same way. Save an earlier index that attains each nonzero maximum. The recurrence is exact: removing the final entry of any longer subsequence leaves an eligible earlier endpoint, and appending to an attaining earlier subsequence achieves the displayed length. Once a label reaches the desired threshold, follow its saved indices backward and reverse the list. Indices strictly decrease during reconstruction, so it terminates. The direct method makes at most pairwise value comparisons; no efficiency claim for arbitrary real-number representations is needed for the existence theorem.
Worked examples
Worked example 2.6.6
(Prefix collisions with negative entries)
Take and the sequence . Its prefix sums are , with remainders modulo .
The equal remainders at indices and give . The corresponding block is . The equal remainders at indices and also give the whole sequence, whose sum is . Several valid answers can exist; the proof needs only one collision.
Comparing the remainders of the entries themselves would not produce this argument. Equal entry remainders establish divisibility of a difference of entries, whereas the goal asks for a sum of consecutive entries.
Worked example 2.6.7
(Five points in a square)
Place any five points in , allowing points on the boundary. Divide each coordinate interval into and . Their four Cartesian products form disjoint boxes, so every point belongs to exactly one box. Two points lie in the same box.
Their two coordinate differences have absolute value at most , so their Euclidean distance is at most
This guarantees a nearby pair without identifying the closest pair. Four points do not suffice for this same guarantee: at the four corners, every pair has distance at least . The point-count threshold is sharp; this statement does not claim the distance constant is optimal among all possible five-point arguments.
Worked example 2.6.8
(Reading the endpoint labels)
For , the endpoint lengths are
For example, because is increasing, while neither earlier increasing subsequence of length can be extended by . Also , attained by or . The last increasing label is , witnessed by or .
Here , so five distinct entries force a monotone subsequence of length . The length-four sequence shows sharpness: an increasing subsequence uses at most one entry from each descending pair, and a decreasing subsequence remains inside one pair. The increasing witness in the first sequence is a subsequence, not a consecutive block.
Common mistakes
Counterexample mode
Strictness and repeated values
Pairwise distinctness cannot be dropped from the strict increasing-or-strict decreasing theorem. The sequence has no strictly monotone subsequence of length , let alone length .
There is a useful replacement that permits equal values: every sequence of real numbers has a nondecreasing subsequence of length or a strictly decreasing subsequence of length . Define the first endpoint label using nondecreasing subsequences. For , either , which extends that label, or , which extends the decreasing label. Thus the same distinct-pair proof works. The equality case must be assigned to one side; it cannot extend a strictly increasing or strictly decreasing subsequence.
Common mistake
(An average is not a bound for every box)
An average occupancy is not a lower bound for every box. Twenty-nine objects in six boxes force some occupancy at least five, but all twenty-nine could be in one box. Similarly, a collision does not identify a unique witness. A proof of existence should not quietly become a claim of uniqueness or of an exact number of solutions.
Common mistake
(Divisibility by is not every residue)
For the divisible-sum theorem, the guarantee is divisibility by the number in its statement. It does not say every prescribed residue occurs as a consecutive sum. For instance, the all-zero sequence has no block sum congruent to modulo when .
Summary
A productive pigeonhole proof starts by describing how failure restricts the possible records. Occupancy bounds restrict each fiber; prefix residues make a collision subtract to a consecutive sum; endpoint lengths make all labels different unless a long monotone subsequence already exists. In each case, check the number of records, the assignment rule and the exact consequence of a collision. A sharp example then shows which threshold is essential and which stronger conclusions the argument does not support.
Exercises
Quick check
(Twenty-nine labeled objects are placed in six boxes. Find the largest occupancy that is always guaranteed, and construct an assignment attaining that guarantee exactly. Must two boxes each contain at least five objects?)
Solution · Answer
The guarantee is . The occupancies have total and maximum , so no larger maximum is guaranteed. Two boxes need not have occupancy at least : has only one such box. These are different extremal questions, and the balanced example answers only the question about the smallest possible maximum.
Quick check
(Three boxes have target occupancies , respectively. Find the least number of objects that forces at least one box to reach its own target, and prove that one fewer does not suffice.)
Solution · Answer
If every target fails, the occupancies are at most , with total at most . Thus objects force some target. With objects, the occupancy vector reaches none of the targets. The least required number is therefore ; averaging with a common threshold would lose the different capacities.
Quick check
(Prove that among any integers two have difference divisible by , for every . Explain why this differs from the consecutive-sum theorem. For , show that entries do not guarantee a nonempty consecutive sum divisible by .)
Solution
Assign the indexed integers to their remainders modulo . Two indices occupy the same box, so subtracting their integer values gives a multiple of . The integers need not be distinct, and a zero difference is permitted.
Here the objects are the original integers. In the consecutive-sum theorem, the objects are the prefix sums formed from original entries; the difference of two prefixes telescopes to a consecutive block. These constructions prove different conclusions. For the sharpness of the entry-count threshold, take entries all equal to . Every nonempty block has sum between and , hence is not divisible by . This example applies for ; for the empty sequence likewise has no nonempty block.
Quick check
(Prove that among seven points in , two have distance at most . Give an arrangement showing that no smaller distance can be guaranteed for every seven-point placement.)
Solution
Partition into the five intervals for and the last interval . They are six disjoint boxes, each of diameter at most . Two of the seven indexed points occupy one box, so their distance is at most .
For sharpness, choose . The smallest distance between distinct positions is . Therefore any proposed uniform bound strictly smaller than fails for this placement.
Quick check
(What does the monotone-subsequence theorem guarantee for thirteen pairwise distinct reals when and ? Construct twelve distinct entries for which neither conclusion holds, and justify both restrictions.)
Solution
Since , the theorem guarantees an increasing subsequence of length or a decreasing subsequence of length . At length , use
An increasing subsequence contains at most one entry from each of the four descending triples, so has length at most . A decreasing subsequence cannot move to a later triple, whose entries are all larger, so has length at most . The two stated conclusions both fail. Merely writing down the arrangement would not establish sharpness without these two arguments.
Quick check
(Explain why the repeated-value replacement in the counterexample block remains true when or . What does it say when ?)
Solution · Answer
The proof uses only the positive integer ranges of the endpoint labels, so it still works when one range has size . If , either there are two entries in nondecreasing order, or every earlier entry is strictly larger than every later one; the entire sequence of length is then decreasing. If , either some earlier entry exceeds a later entry, or all earlier entries are at most all later ones; the whole sequence of length is then nondecreasing. For , it states that any two real entries are nondecreasing or strictly decreasing, exactly the alternatives and .