# Pigeonhole Principle > If you put more things than boxes into the boxes, at least one box must hold two or more things. Page: https://formulabro.yunusemrevurgun.com/computer-science/pigeonhole-principle/ Category: Computer Science Published: 2026-10-22 Updated: 2026-10-22 ## Formula $$ \max_{j}\, b_j \ge \left\lceil \frac{n}{m} \right\rceil $$ Read it out loud: "The largest number of items in any box is at least the ceiling of n over m. Here n is the number of items, m is the number of boxes, and the ceiling of a number means rounding it up to the next whole number. The letter j names a box, and b sub j is the number of items in box j." ## Before you start - **Rounding up, the ceiling $\lceil x \rceil$**: The **ceiling** of $x$, written $\lceil x \rceil$, is $x$ rounded up to the next whole number. For example $\lceil 2.08 \rceil = 3$, because 2.08 rounds up to 3. A whole number is already its own ceiling, so $\lceil 4 \rceil = 4$. Rounding down instead is called the floor, and the principle needs the ceiling, not the floor. - **Dividing to find an average**: A fraction bar means divide. The fraction $\frac{25}{12}$ means 25 items shared among 12 boxes, which is about 2.08 items per box. This is an **average**: the total divided by the number of groups. The average may not be a whole number, even when every item is a whole item. - **Subscripts, like $b_j$**: A small letter placed below another letter is a **subscript**. $b_j$ is read 'b sub j', and it means the number of items in box number $j$. So $b_1$ is the count for box 1, and $b_2$ is the count for box 2. The letter $j$ is a label, not a number of items. - **Maximum, $\max$, and at least, $\ge$**: $\max_{j} b_j$ means the largest value of $b_j$ over all the boxes. If three boxes hold 2, 5 and 1 items, the maximum is 5. The sign $\ge$ means 'greater than or equal to', so 'at least 3' is written $\ge 3$, and it is true for 3 and for 4. - **Proof by contradiction**: A **proof by contradiction** assumes the opposite of what you want to show, and then finds that the assumption leads to something impossible. Here, if every box held at most 2 items, the total would be at most 24. But there are 25 items, so the assumption must be false. - **Hash table and buckets (background)**: A **hash table** stores items by computing a bucket number for each key, using a rule called a hash function. The **buckets** are the numbered slots. Many buckets can hold items, and some buckets can end up with more than one item. That situation is called a collision. More notation help: https://formulabro.yunusemrevurgun.com/math-basics/ ## What each symbol means - $\max_{j}\, b_j$: The number of items in the **fullest box**. The letter $j$ names a box, and $b_j$ is how many items box $j$ holds. The maximum is taken over all boxes, and the result is a count of items, with no unit. - $n$: The **number of items** being placed into the boxes, a whole number such as 25 members. Each item goes into exactly one box. The count has no unit, because it counts things like people, letters or files. - $m$: The **number of boxes**, a whole number of at least 1 such as 12 months. Some boxes may stay empty. The count has no unit, and it is set before the items are placed. - $\left\lceil x \right\rceil$: The **ceiling** of $x$: $x$ rounded up to the next whole number. For example $\lceil 2.08 \rceil = 3$ and $\lceil 4 \rceil = 4$. The result is a whole number of items, so it has no unit. ## The formula piece by piece - $n$: The number of items to place. In the club example, $n = 25$ members. Every item goes into one box, and that is the only rule the principle uses about how the items are placed. - $m$: The number of boxes. In the club example, $m = 12$ months. The principle does not require every box to hold something, so some boxes can stay empty. - $\frac{n}{m}$: The average number of items per box, found by dividing the items by the boxes. For $n = 25$ and $m = 12$ it is $\frac{25}{12}$, which is about 2.08. This average is not a whole number, so it cannot be the count of the fullest box on its own. - $\left\lceil \frac{n}{m} \right\rceil$: The average rounded up to the next whole number. Rounding up, not down, is what the principle guarantees. Since $\lceil 2.08 \rceil = 3$, the fullest box must hold at least 3 items in the club example. - $\max_{j}\, b_j$: The largest count among all the boxes, the count of the fullest box. The principle does not say which box it is, only how big its count must be. - $\max_{j}\, b_j \ge \left\lceil \frac{n}{m} \right\rceil$: In one plain sentence: when $n$ items go into $m$ boxes, the fullest box holds at least $n$ divided by $m$, rounded up to the next whole number. ## What the formula is doing, and why **What goes in and what comes out.** You put $n$ items into $m$ boxes. The principle says that the fullest box must hold a certain minimum number of items. That minimum is $\lceil \frac{n}{m} \rceil$, which is the average $\frac{n}{m}$ rounded up. The principle makes this promise without needing to know where each item went. **Why must it be true?** Suppose every box held at most $\lceil \frac{n}{m} \rceil - 1$ items, which is one less than the minimum. Then all the boxes together hold at most $m$ times that number. But $\lceil \frac{n}{m} \rceil - 1$ is less than $\frac{n}{m}$, so the total is less than $n$. That leaves some items with nowhere to go, which is impossible. So some box must hold at least $\lceil \frac{n}{m} \rceil$ items. **Why is only one box promised?** The rule says nothing about which box is crowded, or how the items got there. It only promises that one box is full enough. That is what makes it useful: you can prove that a repeat or a collision must happen without finding the example itself. **The simplest case and the limits.** The simplest case is $n = m + 1$. Then $\frac{m+1}{m}$ is more than 1 and at most 2, so its ceiling is 2, and some box holds two items. The guaranteed crowding goes up only when $n$ passes a multiple of $m$. If $n$ is at most $m$, the rule guarantees only that one box holds at least 1 item, which says nothing new. ## An everyday picture Think of a coat rack with 4 hooks and 5 coats. Hang every coat on a hook, and at least one hook must carry two coats, because there is no way to avoid it. The average is $\frac{5}{4} = 1.25$ coats per hook, and rounded up that is 2. You do not have to see which hook is crowded to know that a crowded hook exists. ## Worked example: Birthday months in a club A club has 25 members, and each one has a birthday in one of 12 months. The months are the boxes and the members are the items. The question is: what is the least number of members that the fullest month must hold? The answer is a guarantee, and it does not depend on knowing any real birthdays. 1. **Divide the members by the months.** The average per month is $\frac{25}{12}$. Dividing 25 by 12 gives 2 with 1 left over, which is about 2.08 members per month on average. 2. **Round up to the next whole number.** The principle uses the ceiling, which rounds up. So $\lceil 2.08 \rceil = 3$. Rounding up is what makes the promise hold for every possible arrangement of birthdays, not only for the average one. 3. **Test the opposite idea.** Suppose every month held at most 2 members. Then the 12 months together would hold at most $12 \times 2 = 24$ members in total. This is the opposite of what we want to show, so we test it to see if it can be true. 4. **Compare with the real total.** But there are 25 members, and $25 - 24 = 1$ member too many. The assumption that every month holds at most 2 is therefore impossible, so at least one month must hold 3 members. 5. **Notice what the argument did not need.** We never looked at any birthday, and we never named a month. The argument works for any club of 25 members with 12 months, so the guarantee holds for every such club. 6. **Notice why rounding down would fail.** Rounding 2.08 down gives 2. But a club where every month held at most 2 members would hold only 24 members, one short of 25. So 3 is the value the principle can promise, and 2 is too small. **Answer:** The fullest month holds **at least 3 members**. The principle proves this for any club of 25 people, without knowing a single birthday. ## Common mistakes - Expecting the principle to name the crowded month. It proves that a month with at least 3 members exists, but it does not say which month it is. - Rounding down. The floor of $\frac{25}{12}$, which is rounding down, is 2. That is too small. The ceiling, 3, is the value the principle guarantees. - Thinking every box must hold something. Some boxes may stay empty. The rule only sets a lower bound on the count of the fullest box, which is the smallest value that count can have. - Swapping the counts. The items go into the boxes, so $n$ is the number of items and $m$ is the number of boxes. ## Where you will meet it - Hash tables: once there are more keys than buckets, at least two keys must share a bucket, which is a collision. - Lossless compression, which shrinks files without losing any data. No method can shrink every file of a fixed length, because the list of shorter sequences of 0s and 1s, called bits, has fewer entries than the list of files of that length. - Number theory proofs, such as showing that among any 5 whole numbers, two have the same remainder when divided by 4. The remainder is the part left over after dividing. - Scheduling and seating puzzles, where a limited number of slots forces at least one slot to be shared. ## Questions people ask ### Does the principle say which box is crowded? No. It only proves that some box holds at least $\lceil \frac{n}{m} \rceil$ items. It does not name the box, and it does not say how many boxes are crowded. ### Where does the name come from? The picture is pigeons flying into pigeonholes, which are small compartments in a desk or cabinet. With more pigeons than holes, one hole has to hold two pigeons. Some books call the same rule the drawer principle, for the same reason. ### How does it apply to hash collisions? A hash table with $m$ buckets that stores $n > m$ keys must have at least one bucket with two or more keys. The collision cannot be avoided once the keys outnumber the buckets. ## Related formulas - [Hash Table Load Factor](https://formulabro.yunusemrevurgun.com/computer-science/hash-table-load-factor/) - [Birthday Problem](https://formulabro.yunusemrevurgun.com/computer-science/birthday-problem/) - [Combinations](https://formulabro.yunusemrevurgun.com/computer-science/combinations/) ## Sources - [Pigeonhole principle, Wikipedia](https://en.wikipedia.org/wiki/Pigeonhole_principle) - [Floor and ceiling functions, Wikipedia](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) From Formula Bro (https://formulabro.yunusemrevurgun.com/), a side project developed by yunusemrevurgun.com.