Pigeonhole principle

Imagine you have many birds.

You have only a few nests. Some nests must have two birds. This is a rule of counting.

It helps us find things. For example, if you grab three socks, two must be the same color. It works for people too. In London, some people have the same number of hairs. This rule is also called the drawer principle. It helps us solve puzzles.

Imagine you have many birds.

You have only a few nests. If you have ten birds but only nine nests, at least one nest must hold more than one bird. This is a rule of counting called the pigeonhole principle.

This idea helps us solve puzzles. For example, if you pick three socks from a drawer with black and blue socks, two must be the same color. It also works with birthdays. If you have 367 people, at least two must share a birthday. This is because there are only 366 possible birthdays.

Some people call this the drawer principle. A man named Peter Dirichlet wrote about it in 1834. He used the idea of putting pearls into drawers. The name comes from small boxes in desks used to sort papers.

We can even use it to learn about people. A person can have about one million hairs on their head. London has more than one million people. This means at least two people in London must have the same number of hairs. It is a simple way to prove things are true.

Imagine you are sorting items into containers. If you have more items than you have containers, something special must happen. At least one container will end up holding more than one item. This simple idea is called the pigeonhole principle. It is a type of counting argument used in mathematics. It helps us prove things that might seem surprising at first.

You can see this with a small group of objects. If you have three gloves, two must be right-handed or two must be left-handed. This is because there are only two categories of handedness for three objects.

This principle works like a rule for sharing or grouping. For example, think about picking socks from a drawer. If you have black socks and blue socks, you only have two colors. If you pull out three socks, you are guaranteed to have a matching pair. The colors are the holes, and the socks are the pigeons.

You can also use it to think about birthdays. There are 366 possible birthdays, including February 29. If you gather 367 people, at least two people must share a birthday. This is a certain way to find a match.

History shows us that people have used this idea for a long time. The first written reference appears in 1622. A French writer named Jean Leurechon mentioned it in his work. He noted that two men must have the same number of certain items. Later, in 1834, Peter Gustav Lejeune Dirichlet wrote about it. He called it the drawer principle or the shelf principle. He used the idea of putting pearls into drawers to explain it.

We can use this math to look at huge numbers in the real world. Let us look at the people living in London. A human head can have about one million hairs. London has a population of more than one million people. Because there are more people than possible hair counts, a match must exist. In fact, if London has 9.002 million people, at least ten people must have the same hair count. This shows how math works even with very large groups.

This principle connects to many different parts of science and technology. In computer science, it is used in a process called hashing. Hashing maps large amounts of data into smaller, fixed sizes. Since there are often more pieces of data than hash codes, some data must share a code. It also helps explain how computer files are compressed. If a program makes some files smaller, it must make other files larger. This keeps the math of the data balanced and true.

{ "text": "The pigeonhole principle is a fundamental counting argument in mathematics. It states that if you distribute a set of items into a smaller number of containers, at least one container must hold more than one item. This principle may seem obvious, yet it serves as a powerful tool for proving unexpected results. In formal mathematics, it is described using the concept of functions. It asserts that there is no injective function from a larger set to a smaller one. An injective function, or one-to-one function, is one where every input maps to a unique output. If the number of possible outputs is smaller than the number of inputs, a collision is mathematically inevitable.\n\n

\n\nThe mechanism of the principle relies on the relationship between the number of objects and the number of available categories. If you have $n$ items and $m$ containers, and $n$ is greater than $m$, then at least one container must contain at least $\lceil n/m \rceil$ items. The symbol $\lceil \dots \rceil$ represents the ceiling function, which rounds a number up to the nearest whole integer. For example, if you have ten pigeons and nine holes, at least one hole must contain two pigeons. If you have eleven pigeons and five holes, at least one hole must contain at least three pigeons. This logic creates a guaranteed minimum for how items must be distributed.\n\nThere are several ways to generalize this principle for different mathematical contexts. In its most basic form, it deals with finite sets, such as a specific number of socks or people. However, it can also be applied to infinite sets that cannot be placed into a one-to-one correspondence. Mathematical proofs, such as Siegel's lemma, build upon these more advanced, generalized concepts. The principle can also be expressed through various quantitative versions. These versions help mathematicians calculate the exact minimum number of items required to guarantee a certain result in a group.\n\n

\n\nThe history of the principle includes several notable figures and eras. The earliest written reference appears in 1622 in a work by the French Jesuit Jean Leurechon. He noted that two men must share the same number of certain items, such as coins or hairs. In 1834, the German mathematician Peter Gustav Lejeune Dirichlet provided a formal treatment of the idea. He referred to it as the drawer principle or the shelf principle. Dirichlet often used the metaphor of distributing pearls into drawers to explain the concept. Over time, the term \"pigeonhole\" became the standard English name, likely due to the small compartments in desks used for sorting papers.\n\n

\n\nWe can see the principle's significance when applied to large-scale real-world data. Consider the population of London and the number of hairs on a human head. A typical human head has an average of about 150,000 hairs, and it is reasonable to assume no one has more than 1,000,000. Since London's population is much larger than one million, the principle requires that at least two people in London have the exact same number of hairs. If London has a population of 9.002 million, the principle proves an even stronger fact. In that specific case, at least ten Londoners must share the same hair count.\n\n

\n\nOther surprising examples demonstrate how the principle works in social and logical settings. In a group of 367 people, there is a 100% probability that at least two people share a birthday, because there are only 366 possible days. In a hand-shaking scenario, the principle proves that in any group of people, at least two individuals must have shaken the same number of hands. This is because the number of possible handshakes per person is limited. Even in simple tasks like picking socks, if you have two colors of socks, picking three socks guarantees a matching pair. These examples show how the principle forces certain outcomes even when we cannot see them.\n\n

\n\nThe principle connects deeply to modern computer science and complex mathematical analysis. In computer science, it is vital to the study of hashing. Hashing maps large datasets to fixed-size values called hash codes. Because the number of unique objects is often larger than the available hash codes, some objects must inevitably share the same code. The principle also explains the limits of lossless compression algorithms. If a program makes some files smaller, the principle dictates that it must make other files larger. This ensures that the mathematical mapping between the original data and the compressed data remains unique and recoverable.", "media": [ "File:TooManyPigeons.jpg", "File:Pigeon-hole messagebox 3.jpg", "File:Dudeney_no_3_pawns_in_line.svg" ] }