At a dinner party, many of the guests exchange greetings by shaking hands with each other while they wait for the host to finish cooking.
After all this handshaking, the host, who didn't take part in or see any of the handshaking, gets everybody's attention and says: "I know for a fact that at least two people at this party shook the same number of other people's hands."
How could the host know this? Note that nobody shakes his or her own hand.
Assume there are N people at the party.
Note that the least number of people that someone could shake hands with is 0, and the most someone could shake hands with is N-1 (which would mean that they shook hands with every other person).
Now, if everyone at the party really were to have shaken hands with a different number of people, then that means somone must have shaken hands with 0 people, someone must have shaken hands with 1 person, and so on, all the way up to someone who must have shaken hands with N-1 people. This is the only possible scenario, since there are N people at the party and N different numbers of possible people to shake hands with (all the numbers between 0 and N-1 inclusive).
But this situation isn't possible, because there can't be both a person who shook hands with 0 people (call him Person 0) and a person who shook hands with N-1 people (call him Person N-1). This is because Person 0 shook hands with nobody (and thus didn't shake hands with Person N-1), but Person N-1 shook hands with everybody (and thus did shake hands with Person 0). This is clearly a contradiction, and thus two of the people at the party must have shaken hands with the same number of people.
Pretend there were only 2 guests at the party. Then try 3, and 4, and so on. This should help you think about the problem.
Search: Pigeonhole principle
One day a really rich old man with two sons died. In his will he said that he would give one of his sons all of his fortune. He gave each of his sons a horse and said they would compete in a horse race from Los Angeles to Sacramento, but the son whose horse came in second would get the money.
So one day they started the race. After one whole day they had only ridden one mile. At night they decided they should stop at a hotel. While they were booking in they told their problem to the wise old clerk, who made a suggestion. The next day the two brothers rode as fast as they could. What did the clerk suggest that they do?
The clerk told them to swap horses. The father said that whoever's horse crossed the finish line second would get the money. He didn't say that the owner of the horse had to be on it.
Bruce is an inmate at a large prison, and like most of the other prisoners, he smokes cigarettes. During his time in the prison, Bruce finds that if he has 3 cigarette butts, he can cram them together and turn them into 1 full cigarette. Whenever he smokes a cigarette, it turns into a cigarette butt.
One day, Bruce is in his cell talking to one of his cellmates, Steve.
"I really want to smoke 5 cigarettes today, but all I have are these 10 cigarette butts," Bruce tells Steve. "I'm not sure that will be enough."
"Why don't you borrow some of Tom's cigarette butts?" asks Steve, pointing over to a small pile of cigarette butts on the bed of their third cellmate, Tom, who is out for the day on a community service project.
"I can't," Bruce says. "Tom always counts exactly how many cigarette butts are in his pile, and he'd probably kill me if he noticed that I had taken any."
However, after thinking for a while, Bruce figures out a way that he can smoke 5 cigarettes without angering Tom. What is his plan?
Bruce takes 9 of his 10 cigarette butts and turns them into 3 cigarettes total (remember, 3 cigarette butts can be turned into 1 cigarette). He smokes all three of these, and now he has 4 cigarette butts.
He then turns 3 of the 4 cigarette butts into another cigarette and smokes it. He has now smoked 4 cigarettes and has 2 cigarette butts.
For the final step, he goes and borrows one of Tom's cigarette butts. With this cigarette butt plus the 2 he already has, he is able to make his 5th cigarette to smoke. After smoking it, he is left with 1 cigarette butt, which he puts back in Tom's pile so that Tom won't find anything missing.