I have been teaching mathematics in an Australian High School since 1982, and I am a contributing author to mathematics text books.
Perhaps the title does not do justice to Elizabeth Barrett Browning’s famous sonnet 43, but it does draw attention to the essence of this article.
We don’t think twice about the act of shaking someone’s hand as a gesture of greeting or farewell. Your patience might be tested, however, if you attend a party and are obliged to shake hands with fifty people.
Now let’s see what else might happen at the party in addition to your handshaking. If everyone is on good terms with one another, it may be safely assumed that, at some stage, each person will have shaken hands with every other person.
This scenario provides the essence of what is known in mathematics as the Handshake Problem.
In its general form, the problem can be stated as:
In a room of N people, how many handshakes will there be if each person shakes hands once only with every other person.
Let’s begin the investigation with two people, Adam and Sally. They shake hands before their meeting, so there is only one handshake involved.
At the next meeting, the attendees are Adam, Sally and Samir, where three handshakes take place.
With four people, one could list each combination and then determine the total number, but this approach is laborious and mathematically inelegant. A better approach is the following.
Imagine eight people sitting around a table, ready to shake hands. The number of ways this can be done is still the same as eight people randomly placed in a room, but by focusing the problem in this ‘circular’ way, it will make it easier to see patterns that will form the basis of conclusions.
Start by choosing person A as the reference point, but any of the eight people can be chosen.
Person A shake hands with the other seven people. This can be shown as arrows connecting two people at a time. Now use person B as the reference point and show B shaking hands.
Note that this is everyone else but it excludes person A, since A shook hands with B when A was the reference person.
Continuing in this clockwise manner, use persons C, D, E, F and G as reference point.
We stop at G because person H has already shaken hands with everyone else.
There is a pattern to the total number of handshakes with respect to a given person.
It can be concluded that the total number of handshakes for 8 people (A to H) is 1+2+3+4+5+6+7 = 28.
This is the sum of the first 7 natural (whole) numbers.
Using a similar method, the total number of handshakes for up to 8 people is shown below.
From the table it can be concluded that the total number of handshakes is the sum of the first set of whole numbers up to one less than the number of people.
For N people, the number of handshakes is the sum of the first N - 1 whole numbers.
Thus, for 9 people, the number of handshakes will be 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36, and for 10 people it will be 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45.
This approach works satisfactorily, but what would be the situation if there are 100 people?
The brute force approach will be to calculate 1 + 2 + 3 + 4 +….. all the way up to 99.
It will work, but in mathematics, elegance and efficiency is always a priority. With this in mind, the number pattern 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 +… is called an arithmetic series and there is a formula that gives the sum without the need for laborious, repetitive calculations.
For our arithmetic series, the number we use is one less than the number of people. That is, we use n = N – 1.
Also, the first number of the series is 1 (a = 1) and the difference between two consecutive terms is 1 ( d = 1).
Substituting n = N – 1, a = 1 and d = 1 into the formula gives
Applying the formula to 8 people confirms that there are 28 handshakes.
The connection with Combinations
The Handshake Problem formula can be explained using combinatorial mathematics.
Firstly, the number of combinations when choosing r objects from n objects is given by the expression
The notation ! means factorial, with n! = n(n - 1)(n - 2)(n - 3)….3 x 2 x 1, and we take 1!=1 and 0!=1.
For example, 4! = 4 x 3 x 2 x 1 = 24.
Thus, the number of ways of choosing 2 objects from 3 objects is
This corresponds to our earlier example when we established that Adam, Sally and Samir combined shake hands three times. The significance of taking 2 at a time is that only two people shake hands at one time.
For instance, if we allowed the ludicrous situation where one person shakes the hands of two other people at the same time, then for Adam, Sally and Samir we would be working out
This means all three people shake hands at the same time, and there is only one way of doing that.
If there were four people, say, A, B, C and D, the number of ways will be
The combinations are A(BC), A(BD), A(CD), B(CD), where, for example, A(BC) means A shakes hands with B and C at the same time.
So we can generalise.
So, next time you go to a party, be sure to shout out, “only one handshake per customer!”