Pigeonhole Principle

This is a very simple idea that can come in handy when trying to sort things into different categories. Suppose you run a hotel and have 40 guests and 40 rooms for them to stay in. Each of them can have their own room. What if you didn't have enough rooms but didn't want to turn anyone away? At least two people will be heading toward the same room number!

Consider this classic example: You go to a party and meet a bunch of people. There are n people at the party, which means that there are n-1 other people whose hands you can shake. Everyone shakes at least one person's hand. By the pigeonhole principle, since there are n people and less than n number of people's hands to shake, when categorizing people by the number of hands that have been shaken, there must be at least two people that have shaken the same number of hands.

This idea comes in handy in computer science in things like hash functions.

See w:Pigeonhole_principlewikipedia for more information.