Saturday, February 16, 2013

Handshake Problem

Let me start by giving a little math problem. n people are in a room, and each one has to shake every other person's hand. How many handshakes will it take for all n people to have shaken every other hand?

Let's first try a few numbers. For two people, it would obviously just take one handshake. For three, it would take three handshakes. For four, it would take six handshakes. For five, it would take ten handshakes.

Do you see the pattern? 1, 3, 6, and 10 are the triangular numbers. In fact, this pattern always continues. 

If you look at it logically, you will see why. Person 1 has a number of hands to shake. Person 2 would have to shake all of the hands except for person 1's (it was already counted). Each person has to shake one less than the one before until there is just one left.

Adding up these handshakes will be a sum of the first n natural numbers, which is the definition of triangular numbers. 

I found it cool that a famous number sequence could be applied to a practical problem like this. 

No comments:

Post a Comment