Pigeonhole principle and counting arguments

Four socks, three colours: what must repeat?

A drawer contains socks in exactly three possible colours. You take four socks without looking; assume at least four are available. Each sock has one colour. Could all four have different colours? The first three could use all three colours, but a fourth cannot introduce a fourth colour. At least two of the four socks share a colour, though you cannot yet say which colour or which socks.

The objects are the individual socks, not the colours. The three categories are colour labels. Even two socks that look alike are different objects when counting how many were taken. In the diagram, numbers identify the socks and boxes identify their categories; the drawn arrangement is one example, rather than a prediction of the actual draw.

Useful preparation is integer division with remainders, comparing inequalities, functions with a declared input and target, and reasoning from a general rule. The linked lessons are already published. Every mapping and counting definition needed here is stated locally; the later set and proof lessons are optional background, not prerequisites.

On a first reading, follow the socks, single-assignment proof, ceiling bound and capacity examples. Then choose the remainder application or the square diagram. Return to the floor proof and the general spatial inequality after you can explain why each object belongs to exactly one category. The choice tree is a short reminder of how to count categories accurately.

Every object goes into exactly one category

Let A be a finite set of n distinct objects and B a finite set of m categories. Here n is a nonnegative integer and m is a positive integer. The notation |A| = n gives the number of elements of A. A function f: A → B assigns exactly one category in B to each object in A. Categories may be empty; an object may not be left unassigned or counted in two categories.

For category i, let aᵢ be its number of assigned objects. The counts are nonnegative integers and a₁+⋯+aₘ = n. This sum is the bridge from the assignment to the conclusion. If categories overlap before assignment, specify a unique ownership rule first; otherwise their separate counts can double-count an object.

The finite pigeonhole principle says: if n > m, then at least one category contains at least two objects. Suppose instead that every category contains at most one. Adding the m counts would give n ≤ m, contradicting n > m. Therefore there are different objects x and y with f(x) = f(y). This is called a collision; the objects remain distinct even though their categories agree.

The condition is strict. When n = m, one object per category is possible. A collision is also possible, as counts (2, 0, 1) show when n = m = 3. When n < m, a collision can still occur, but the counts alone do not force it. The theorem gives a sufficient condition, not an if-and-only-if test for actual collisions.

Distinct outputs require enough available categories

A function is injective when different inputs always have different outputs. Equivalently, each output category holds at most one input. For a function between finite sets, injectivity therefore implies n ≤ m. This is the contrapositive of n > m forcing noninjectivity: if no collision occurs, the source cannot be larger than the target.

Do not reverse that implication. The inequality n ≤ m does not make a particular function injective: two inputs can both be assigned to the first category even when many others are unused. With no additional restrictions, n ≤ m does allow some injective assignment, obtained by choosing n different categories. Existence of an injective assignment and injectivity of the assignment in front of you are different claims.

If m = 0, a nonempty source has no function into that target at all; an empty source has the empty function. We require m ≥ 1 for the box averages below so that division by m and a statement about some category make sense. The argument is finite: an infinite source and infinite target cannot be compared by subtracting or averaging their sizes in this way.

The average forces a large category and a small one

For a real number t, ⌈t⌉ is the smallest integer at least t and ⌊t⌋ is the largest integer at most t. For example ⌈11/4⌉ = 3 and ⌊11/4⌋ = 2, while both rounded values of 12/4 equal 3. Counts are integers, so the rounding directions matter.

With n ≥ 0 objects assigned to m ≥ 1 categories, some category has at least ⌈n/m⌉ objects. Write c = ⌈n/m⌉. If all categories had fewer than c, each would have at most c−1. Their total would be at most m(c−1), which is strictly smaller than n because c−1 < n/m. This contradicts their actual total n.

Some category also has at most ⌊n/m⌋ objects. Put q = ⌊n/m⌋. If every category had more than q, each integer count would be at least q+1. The total would be at least m(q+1) > n because q+1 > n/m. Thus that assumption is impossible.

For n = 0, every category is empty: both guarantees say that some category has at least 0 and some has at most 0. They do not produce an object or a pair. If m = 1, its sole count is exactly n. For n > m, the ceiling is at least 2, recovering the basic principle.

For eleven objects in four categories, the ceiling guarantees a category of size at least 3 and the floor guarantees a category of size at most 2. These may be different categories. The conclusion is not that every category has 3, nor that any chosen category has 3. Counts (8, 1, 1, 1) satisfy both guarantees just as counts (3, 3, 3, 2) do.

Balanced arrangements show exactly how sharp the bound is

Integer division writes n = mq+r with q ≥ 0 and 0 ≤ r < m. Place q+1 objects in r categories and q in the other m−r categories. When r = 0 all counts equal q; otherwise their largest count is q+1. In both cases the maximum equals ⌈n/m⌉ and the minimum equals ⌊n/m⌋.

This construction proves sharpness: using only n and m, you cannot promise a larger minimum value for the largest category, or a smaller maximum value for the smallest category. An unbalanced arrangement may have a much larger category; a universal guarantee must also survive the balanced arrangement.

Divisibility alone does not force equal counts. Twelve objects in four categories might have counts (9, 1, 1, 1). But if n = mq and every category is at most q, all must equal q: a count below q would make their sum less than mq. Likewise, if all are at least q and their sum is mq, none can exceed q. The total plus the individual bounds force equality.

A capacity bound becomes a strict forcing threshold

Choose a nonempty family of m categories. Suppose each count is required to lie between integers L and U, where 0 ≤ L ≤ U. Summing the individual bounds gives mL ≤ n ≤ mU. These bounds are necessary for that requirement to be possible. With unrestricted assignment among the categories they are also sufficient: start with L in each, then distribute the n−mL remaining objects into at most U−L free places per category.

If n > mU, some count must exceed U; equality n = mU does not force an excess. In integer terms the first forcing total is mU+1. If n < mL, some count must fall below L; equality n = mL does not force a shortage. This lower-threshold statement has a possible antecedent only when L > 0, because n cannot be negative.

To force at least k objects in one category, with integer k ≥ 1, rule out the avoidance arrangement in which every count is at most k−1. The sharp threshold is n ≥ m(k−1)+1. At n = m(k−1), putting k−1 in every category avoids the goal. For k = 1, one object suffices; zero objects do not.

For three categories and a maximum of two each, six objects can fit as (2, 2, 2), whereas seven force some category above two. For a minimum of two each, six permit (2, 2, 2), whereas five force a count below two. A capacity requirement is not a physical promise that an impossible arrangement will somehow fit; crossing the bound proves that at least one requirement must fail.

Add disjoint cases; multiply successive choices

Before applying a counting bound, count the categories accurately. If each object is in exactly one of several disjoint groups, add the group sizes. Disjoint means no object belongs to two of the groups. If two groups overlap, adding their sizes counts shared objects twice; first give them unique ownership or subtract the shared count once.

For successive choices, count the complete paths. If a first choice has two possibilities and each has three possible second choices, the six ordered outcomes are (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3). The product 2×3 counts each path once. It requires three continuations for every first choice; no probabilistic independence assumption is involved.

If the first branch has three continuations but the second has only two, the total is 3+2 = 5, not 2×3. The tree makes the missing path visible. Once you have identified six genuinely distinct categories, seven objects assigned to them force a collision; if you accidentally count one category twice, that guarantee can be weakened or misapplied.

Equal remainders give a divisible difference

Fix a positive integer m. Each integer a, including a negative one, has a unique expression a = qm+r with integer q and remainder 0 ≤ r < m. Assign a to its remainder r. There are exactly m categories, labelled 0, 1, …, m−1; a negative integer does not create a new negative-remainder category.

Among m+1 distinct integers, two must have the same remainder. If a = qm+r and b = pm+r, subtracting gives b−a = (p−q)m, a multiple of m. The integers are distinct, so their difference is nonzero. The theorem does not say that one of the original integers is divisible by m, nor that their sum is divisible by m.

For m = 5, the six integers −7, −2, 0, 3, 8 and 11 have remainders 3, 3, 0, 3, 3 and 1. One witness is −7 and −2: their difference is 5. The assignment table finds actual witnesses; the counting argument establishes that a witness exists for every choice of six distinct integers.

If the inputs are repeated observations rather than a set of distinct integer values, treat their positions as the objects. Two observations of 2 share a remainder and have difference 0, which is divisible by m. That is a valid collision of positions, but it is not a pair of distinct integer values with a nonzero difference. State which kind of object the application requires.

A large group is not necessarily your group

A partition of a finite set separates its members into nonempty disjoint groups whose union is the whole set. The groups can be the categories in the principle. If a class of 25 learners is partitioned into six project groups, some group contains at least ⌈25/6⌉ = 5 learners. The theorem does not identify that group or say that all six contain five.

A month-of-birth assignment has twelve possible categories even if some are empty. Thirteen people force two with the same birth month. Twelve people may already have many shared months, but one per month avoids a collision. This is a deterministic guarantee; no randomness, equal likelihood of months or independence of birthdays is needed.

You cannot infer that another person shares your own month. All twelve other people could have one different month. More generally, existence of some repeated category does not select a prescribed category, the final object, or a prescribed pair. To find a witness in a finite dataset, compute the categories and compare their members; the proof and the search answer different questions.

Five points in a square force a close pair

Take five distinct points in the closed unit square: coordinates satisfy 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1, in the same length unit. Divide each coordinate interval into a low half [0, 1/2) and a high half [1/2, 1]. The bracket includes an endpoint and the parenthesis excludes it. A midpoint belongs to the high half; an outer endpoint belongs to its containing half.

Assign a point by its low-or-high x and low-or-high y. These four categories are disjoint and include every point, including points on the dividing lines. In the diagram category labels are 0 for low-low, 1 for high-low, 2 for low-high and 3 for high-high. Since 5 > 4, two points share a category.

For two points in one category, |Δx| ≤ 1/2 and |Δy| ≤ 1/2. The Pythagorean distance d satisfies d² = (Δx)²+(Δy)² ≤ 1/4+1/4 = 1/2, hence d ≤ √2/2 length units. The drawn axes use the same scale. Choosing a unique boundary owner supplies a valid function; closed bounding squares still give the inclusive distance bound.

The conclusion cannot be strengthened to d < √2/2 for every set of five points. Put points at the four outer corners and the centre. Centre-to-corner distances equal √2/2; corner-to-corner distances are 1 or √2, so the shortest distance is exactly √2/2. Nor does the principle identify which two points will share a category before their coordinates are supplied.

Four corner points occupy four different categories and have no distance at most √2/2. This shows why five is needed for this guarantee. The distance proof concerns arbitrary points in the continuous square; the finite plotted cases illustrate its assignment and witnesses, rather than proving the general result by sampling.

Worked examples

Try it yourself

1. Five objects are assigned to five categories. Must the assignment be injective? Must it have a collision? Give arrangements supporting your answer.

   Show the answer and reasoning

   Neither is forced. Counts (1, 1, 1, 1, 1) are injective; (2, 0, 1, 1, 1) contain a collision.

   Both arrangements have five objects and five categories. The theorem requires n > m to force noninjectivity. The necessary condition n ≤ m for injectivity does not establish that a particular assignment is injective.

2. What do the ceiling and floor statements say for zero objects in four categories, and for seven objects in one category?

   Show the answer and reasoning

   For zero objects every count is 0, so both bounds are 0 and no pair exists. With one category its count is exactly 7.

   The family of categories is nonempty in both cases, so statements about some category are meaningful. For m = 1, both rounded values equal n. The zero-object guarantee is about empty counts, not the existence of an object.

3. Find the ceiling and floor guarantees for 25 objects in six categories. Give a balanced arrangement proving both bounds sharp.

   Show the answer and reasoning

   Some category has at least 5, and some has at most 4. Counts (5, 4, 4, 4, 4, 4) attain these bounds.

   25 = 6×4+1, so one balanced category gets 5 and the remaining five get 4. The maximum is 5 and minimum 4. These are statements about some categories, potentially different ones, rather than about every category.

4. Twelve objects occupy four categories. Does divisibility by four force all counts to equal three? What additional upper bound would force this?

   Show the answer and reasoning

   No: (9, 1, 1, 1) is possible. If each count is at most 3, their total 12 forces all four to equal 3.

   Four counts each at most three have maximum possible total twelve. If one were smaller, the others could not compensate without exceeding three. The individual bound together with the total proves equality; divisibility alone does not.

5. What is the least total that forces at least five objects in one of four categories? Show why one fewer is insufficient.

   Show the answer and reasoning

   17 objects force five. At total 16, counts (4, 4, 4, 4) avoid five.

   Avoiding five means every count is at most four, with total at most sixteen. A seventeenth object crosses the strict capacity bound. The exhibited avoidance arrangement verifies that the guarantee cannot begin earlier.

6. Each of four categories must contain between two and five objects. What total range is possible with unrestricted assignment? What do totals 7 and 21 force?

   Show the answer and reasoning

   The possible totals are every integer from 8 through 20. Total 7 forces a count below 2; total 21 forces a count above 5.

   Start with two objects in each category, totalling eight, and add up to three per category. This achieves all intermediate totals. Seven is below the lower sum; twenty-one exceeds the upper sum. Equality at eight or twenty does not force a violation.

7. One first choice has three continuations and another has two. How many complete paths exist? Separately, two groups have sizes four and three with two shared objects: how many distinct objects are in their union?

   Show the answer and reasoning

   There are 3+2 = 5 paths. The union has 4+3−2 = 5 distinct objects.

   The branch counts are unequal, so multiplying two by three invents a missing path. For the union, the shared objects are counted in both group totals and must each be subtracted once. In each problem, count every final object once.

8. Why do any eight distinct integers contain two whose nonzero difference is divisible by seven? Can you instead conclude that their sum is divisible by seven?

   Show the answer and reasoning

   Eight objects exceed seven remainder categories, so a pair has the same remainder and a nonzero difference divisible by 7. The sum conclusion does not follow.

   Subtracting equal remainders cancels them. Adding would give twice that remainder, which need not be zero modulo seven. Distinctness of the integer values makes the difference nonzero; repeated positions alone would not ensure this.

9. In a group of thirteen people including you, must someone else share your birth month? What shared-month statement is guaranteed?

   Show the answer and reasoning

   Your own month need not repeat. Some two people share a month, but the pair may exclude you.

   The other twelve could all have one month different from yours, so a specified category is not guaranteed a second member. Thirteen people assigned to twelve possible months do force some repeated month, regardless of birthday probabilities.

10. Which category owns (1/2, 1/4), (1/4, 1/2) and (1/2, 1/2)? Can five arbitrary points always guarantee a distance strictly less than √2/2?

    Show the answer and reasoning

    They belong to categories 1, 2 and 3 respectively. No: the four corners and centre have shortest distance exactly √2/2.

    Equality at a midpoint belongs to the high coordinate half, giving unique ownership. The same-category calculation proves an inclusive bound. The exact corner-and-centre arrangement disproves a universal strict bound while attaining the inclusive one.

What to carry forward

• Count finite distinct objects, use a nonempty family of categories, and assign every object exactly once.
• n > m forces a collision. Injectivity implies n ≤ m; the converse does not describe a particular assignment.
• Some count is at least ⌈n/m⌉ and some at most ⌊n/m⌋. Balanced counts show both universal bounds are sharp.
• Exceeding mU forces a count above U; going below mL forces a count below L. Equality alone does not force a violation.
• Identify the categories and ownership rule in each application. Existence of a witness does not specify your category or a chosen pair.