The Pigeonhole Principle Explained With Socks

Imagine you have five socks in your hands and just three drawers to put them in. You start placing the socks one by one. You put one sock in the first drawer, one in the second, and one in the third drawer. Now you have two socks left over.

You dropped the fourth sock into the first drawer and the fifth sock into the second drawer. Look inside the drawers now. The first drawer holds two socks. The second drawer holds two socks and the third drawer holds one sock.

No matter how you tried to arrange those five socks across the three drawers, at least one drawer had to end up with more than one sock. This obvious truth is one of the most powerful tools in mathematics known as the pigeon hole principle. We call it that because you can imagine putting pigeons into pigeon holes. Let us state this rule formally.

If you have a certain number of items and you place them into a smaller number of containers, at least one container must hold more than one item. In mathematics, we use letters to represent these ideas. So, we can use them anywhere. Let the letter N stand for the total number of items you are sorting.

Let the letter M stand for the total number of containers available to hold those items. When your items outnumber your containers, meaning N is greater than M, crowding is guaranteed to happen somewhere. Sometimes you can figure out even more than just a crowded container. Sometimes you can find the exact minimum number of items that must land in the most crowded container.

For that, we use a special math symbol called the ceiling function, which looks like a square bracket with the top half cut off. The ceiling function simply means you take your number of items divided by your containers. And if you get a fraction, you always round up to the next whole number. Let us see this in a real example.

Imagine 10 students walk into a classroom, but there are only nine chairs waiting for them. Here, our items are the 10 students. So, n= 10. Our containers are the nine chairs.

So, m= 9. If you divide 10 students by nine chairs, you get 1 and 1 nth. The ceiling function tells us to round that fraction up to the next whole number, which is two. This guarantees that at least one chair must have two students sharing it.

Let us try a slightly larger example with cards. Suppose you have a deck of 13 cards and you deal them into four separate piles on the table. Here your items are 13 cards. So n equals 13.

Your containers are four piles. So m equals 4. If you divide 13 by 4, you get three with a remainder of 1. The ceiling function rounds that three and a quarter up to the next whole number, which is four.

This proves that at least one of those four piles must contain four or more cards. You might wonder what happens if the number of items equals the number of containers. Suppose you have three socks and three drawers. You can place one sock in each drawer cleanly.

Every drawer gets exactly one sock and no drawer has to double up. So the rule only guarantees crowding when your items strictly outnumber your containers. There is a common misunderstanding to watch out for. This principle guarantees that a crowded container exists, but it never tells you which specific container it is.

It tells you that a shared birthday must exist in a certain room. But it does not tell you whose birthday it is. To see why this rule is rock solid, let us prove it by contradiction. Assume for a moment that the rule is false.

Suppose you have 10 students and nine chairs and every single chair holds at most one student. If every one of the nine chairs holds at most one student, then the total number of seated students can be at most nine. That contradicts our starting fact that we had 10 students. Since our assumption led to an impossible result, the assumption must be wrong which proves the original rule must be true.

You will find this principle hidden everywhere in the real world. Consider birthdays in a standard year. There are 366 possible birthday dates if you include leap day. If you gather 367 people in a room, those people act as your items and the calendar days act as your containers.

Because your people outnumber your calendar days by one, the principle guarantees that at least two people in that room share the exact same birthday. You do not need to check everyone. The math guarantees it before you even start. The pigeon hole principle turns obvious everyday packing problems into absolute mathematical certainties.

Whenever your items outnumber your spaces, crowding is not just likely, it is mathematically unavoidable. Generate your own educational videos for free at eduvids. app. app.