Handel has been killed and Beethoven is on the case. He has interviewed the four suspects and their statements are shown below. Each suspect has said two sentences. One sentence of each suspect is a lie and one sentence is the truth. Help Beethoven figure out who the killer is.
Joplin: I did not kill Handel. Either Grieg is the killer or none of us is.
Grieg: I did not kill Handel. Gershwin is the killer.
Strauss: I did not kill Handel. Grieg is lying when he says Gershwin is the killer.
Gershwin: I did not kill Handel. If Joplin did not kill him, then Grieg did.
Who is the killer?
Strauss is the one who killed Handel. You need to take turns assuming someone is the killer; that means everyone's second sentence is a lie. If Joplin was the killer, Grieg's lie mixed with Strauss' counteracts the other. If Grieg was the killer, Gershwin would need to be a killer too. If Gershwin was the killer, Gershwin would need to be a killer too. If Gershwin was the killer, Grieg and Strauss counter each other again, but with Strauss, everything would fit in.
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