Finite cardinality: force a collision without locating it

A finite set has size n when it can be bijected with n standard positions. If more than n objects are assigned to n positions, the assignment cannot be injective: at least two objects share a position. The conclusion is unavoidable but nonconstructive in a practical sense. It identifies neither the repeated position nor the pair unless the argument is supplemented with a search. It also gives no probability distribution over which collision occurs.

The finite restriction is essential. An infinite set can be bijected with a proper subset, as doubling matches natural numbers with even natural numbers. For finite sets, deleting even one element strictly decreases size. This distinction explains why finite capacity arguments need a genuine finite bound on their categories; saying an unbounded process uses integers is not enough to force a repeated integer. State both the size comparison and the function connecting the two sets.

If N objects occupy m possible boxes, with m positive, at least one box contains the ceiling of N divided by m objects. To prove it, suppose all occupancies were smaller than that integer bound and add their capacities. The resulting total would be too small. A particularly convenient version says that more than km objects force some box to contain at least k plus one. The strict inequality matters exactly at the threshold.

The bound is sharp when objects can be distributed as evenly as possible. For ten objects in three boxes, occupancies four, three, and three show that four is guaranteed but five is not. A guarantee is a worst-case claim across every assignment, not an average outcome. Empty boxes are allowed; saying there are m boxes does not assert every box is occupied. Their existence only supplies an upper bound on the number of possible categories.

Remainders make useful boxes because equal remainders imply divisibility of a difference. Among any six integers, two have the same remainder modulo five, so their difference is divisible by five. Intervals make another choice: divide a bounded range into short pieces, and two points sharing a piece must be close. Assign boundaries carefully so each object enters exactly one box, for example by using half-open intervals except at the final endpoint.

Sometimes the objects to classify are derived quantities rather than the original inputs. Partial sums turn a consecutive-sum problem into a comparison of two sums. If two partial sums share a remainder, their difference is a consecutive block with the desired divisibility. Before invoking the principle, ask what equality of category labels would mean. If sharing a box does not imply the target property, the count may be correct but the proof still misses its goal.