Graph Theory: The same 5 people as last week decide to shake hands  with a different number of people, that is, one with 4 people (you can't shake with 5 - that would include shaking hands with yourself), one with 3 people, etc. Is this possible?

Math Factor podcast

Solution: if each shakes hands with a different number, then someone will have to shake hands with no other person. But then nobody could shake hands with all 4 other people (including the one who shakes hands with no other person). So it is not possible.

For more math puzzles, check out http://www.mathpuzzle.com/, http://mathschallenge.net/, http://www.princeton.edu/~mathclub/puzzles4.html and http://mathforum.org/k12/k12puzzles/