# The pigeon hole principle

## Pigeonhole Principle

• The Pigeonhole Principle is a simple yet powerful mathematical concept. It states if you have more items than containers to put them in, at least one container must hold more than one item.
• It is a form of combinatorial logic, used to draw certain conclusions from given information.
• It is particularly useful in proving the existence of certain outcomes without identifying them specifically.

## Explicit and General Form

• The explicit form states that if `n` items are put into `m` containers, and `n > m`, then at least one container must contain more than one item.
• The general form extends this by stating that if `n` items are distributed in `m` containers, then at least one container must hold at least `⌈n/m⌉` items. Here `⌈n/m⌉` denotes the ceiling function, which rounds a number up to the next largest integer.

## Application

• The principle is used in different branches like discrete mathematics, coding theory, and somewhat unexpectedly, in some areas of computer science – proving its versatility.
• It can help to prove broad statements about the distribution of sets of numbers, useful in certain algebra and number theory problems.
• It doesn’t require a deep understanding of complex mathematical concepts, but often requires creative thinking to see how it can be applied.

## Examples

• A simple realization of the Pigeonhole Principle is the statement: “In any group of six people, at least two must share the same birthday month.”
• Another common example deals with spatial organization. If five socks are chosen at random from a drawer containing just ten socks (five pairs), there must be at least one pair among the chosen socks.

## Limitations

• Remember that while the Pigeonhole Principle proves the existence of certain outcomes, it doesn’t usually provide a method for finding the outcomes.
• Like any mathematical theorem, it applies only under the conditions that its assumptions hold – in this case, that the items and containers are distributed in a certain way.

## Learning Tip

• Practice Pigeonhole Principle problems to become familiar with the way it’s used. Start with simple examples and gradually move on to more complex scenarios.
• Always look for a way to apply the Pigeonhole Principle when presented with problems that involve distributing items across containers in some way.