Pigeonhole principle facts for kids

Imagine fitting ten pigeons into nine small boxes – at least one box will have more than one pigeon!

The pigeonhole principle is a cool idea in mathematics that helps us solve tricky problems. It says that if you have more items than you have places to put them, then at least one place must have more than one item.

Think of it like this: if you have 10 pigeons and only 9 pigeonholes (small boxes for pigeons), then at least one pigeonhole must have two or more pigeons inside. The "pigeons" and "pigeonholes" are just examples. You can use this idea for anything, like socks and colors, or students and classrooms.

This principle is very useful in areas like computer science and different parts of mathematics, especially in something called graph theory.

What is the Pigeonhole Principle?

The pigeonhole principle is a simple but powerful rule. It states that if you have a set of items (like pigeons) and you want to put them into a smaller number of containers (like pigeonholes), then at least one container will end up with more than one item.

For example, if you have three gloves and only two hands, you must have at least two gloves on one hand. This principle helps us understand situations where things are grouped together.

How Does the Pigeonhole Principle Work?

This principle works because it's impossible to spread out a larger number of items into a smaller number of spaces without some spaces getting crowded. It's often used to prove that something must happen, even if we don't know exactly where or how.

It's a bit like saying if you have 13 students and only 12 months in a year, then at least two students must share the same birthday month.

Everyday Examples of the Principle

Let's look at some fun ways the pigeonhole principle appears in daily life:

Socks in a Drawer

Imagine you have a drawer with 12 blue socks and 18 black socks. You're trying to get a matching pair, but it's dark, and you can't see the colors. How many socks do you need to pull out to be sure you have a pair of the same color?

• Think of the colors (blue and black) as your "holes" or categories. You have 2 colors.
• If you pull out just one sock, you don't have a pair.
• If you pull out two socks, they could be one blue and one black. Still no pair!
• But if you pull out a third sock, it must be either blue or black. No matter what color it is, it will match one of the first two socks you pulled out. So, you are sure to have a pair of the same color.
• The answer is 3 socks. This is because 3 is more than the 2 possible colors (holes).

Birthdays in a Group

If you gather a group of people, how many people do you need to have to be sure that at least two of them share the same birthday month?

• There are 12 months in a year. These are your "holes."
• If you have 12 people, it's possible they all have different birthday months.
• But if you have 13 people, then at least two people must share the same birthday month. This is because 13 is more than 12.

Importance in Computer Science

The pigeonhole principle is very important in computer science. For example, it helps computer scientists understand how much memory is needed for certain tasks or how efficient a computer program can be. It can also be used to prove that some problems are impossible to solve in a certain way.

It's a basic idea that helps build more complex theories and systems in the world of computers.

Images for kids

• 

  Pigeon-hole messageboxes at Stanford University

See also

• Mathematical principles