How Many Handshakes at a Party of 30?

Small parties

Here are the parties the widget counts. Fill in the ones you haven’t done before you look.

Look at the last column. Each time one more person comes to the party, the handshakes go up by one more than the time before: 2, then 3, then 4. Why?

The newcomer

Think of the people arriving one at a time. The first sits down alone: no handshakes. The second shakes 1 hand. The third shakes hands with the two already there: 2 more. The fourth shakes 3. Each newcomer shakes hands with everyone already in the room, and that is one more person each time. The widget’s “Next person shakes” button counts this way.

So when the eighth person walks in, they add 7 handshakes, and a party of 8 has 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. And for the class of 30, the thirtieth student shakes 29 hands as they come in, so the class has

$$1 + 2 + 3 + \dots + 28 + 29$$

handshakes. That is a long sum. Is there a quicker way to do it?

Adding in pairs

Write the sum forwards and backwards, and add the two lines in pairs:

Every pair makes 30, and there are 29 pairs. So twice the sum is 29 × 30 = 870, and the sum itself is half of that: 435.

Or pair the numbers inside one line: 1 + 29, 2 + 28, 3 + 27, all the way to 14 + 16. That is 14 pairs of 30, which is 420, with 15 left in the middle by itself: 420 + 15 = 435. Either way, nobody has to add 29 numbers one by one.

The pairing gave 435. Now count the same handshakes in two other ways, and see that they agree.

Way 1: one newcomer at a time

This is the count you just did: 1 + 2 + 3 + … + 29 = 435. Draw it with dots, one row for each newcomer, and it makes a staircase.

Make a copy of the staircase, turn it round, and fit it against the first. Every row now has the same number of dots, and the two staircases fill a rectangle. For a party of 6, Figure 11.1 shows rows of 1 + 5, 2 + 4, 3 + 3, 4 + 2 and 5 + 1: a rectangle of 5 rows of 6, 30 dots. So the staircase alone is half of it, 15. This is the adding-in-pairs trick drawn as a picture.

For the class of 30 the staircase has 29 rows, and the rectangle is 29 rows of 30: half of 870, 435.

Way 2: everyone counts their own

Now ask each student, when it is over, how many hands they shook. Every one of them says 29, everyone but themselves. (The number in each circle of the widget, once a party is finished, is one less than the number of people.) Thirty students, 29 each: 30 × 29 = 870.

But 870 is too many. When Gita and Bibek shake hands, Gita counts it, and Bibek counts it too. Every handshake is counted twice, once by each of the two hands in it. So the real number is half: 870 ÷ 2 = 435.

That is also what was wrong with Bibek’s 900. He counted 30 for each person, as if everyone shook their own hand too, and then he forgot that each handshake has two people in it.

Way 3: a table of who shook whose hand

Make a table with a row and a column for each person. Put a tick where the row’s person shook hands with the column’s person. Figure 11.2 shows a party of six, by their first letters: Anu, Bibek, Dawa, Esha, Gita and Hari.

The table has 6 × 6 = 36 boxes. Six of them, along the diagonal, are each person and themselves: cross those out, and 30 are left. And each handshake has two boxes: Anu with Bibek is the box in row A, column B, and also the box in row B, column A. So there are 30 ÷ 2 = 15 handshakes, the boxes above the diagonal.

For the class of 30, the table has 30 × 30 = 900 boxes. That is Bibek’s 900! Take away the 30 on the diagonal: 870. Halve it: 435. So Bibek counted every box of the table, and the table shows exactly what to take away.

Counting pairs

A handshake is a pair of people. Two people in it, and it doesn’t matter which you name first: Gita shaking Bibek’s hand is the same handshake as Bibek shaking Gita’s. So the question “how many handshakes?” is really: how many different pairs can you make from 30 people?

All three counts above say the same thing. Each person can be paired with every other person, and each pair is then counted from both ends, so for a group of n people:

$$\text{number of pairs} = \frac{n \times (n - 1)}{2}$$

In Grade 7’s algebra, it is the expression $\frac{n(n - 1)}{2}$. For n = 30: $\frac{30 \times 29}{2} = 435$. For n = 6: $\frac{6 \times 5}{2} = 15$. The formula isn’t a rule to learn by heart: it is Way 2 written in letters. n people, n − 1 hands each, halved because every handshake has two ends.

Counting the same thing in two ways, and setting the answers equal, is called double counting. It is one of the most useful ideas in counting: Way 1 and Way 2 count the same handshakes, so their answers must be the same, and that proves the pairing trick: 1 + 2 + 3 + … + (n − 1) is always $\frac{n(n - 1)}{2}$.

Mathematicians write the number of pairs from n things as ${}^{n}C_{2}$, and say it “n choose 2”: the number of ways of choosing 2 things out of n, when the order doesn’t matter. So ${}^{30}C_{2} = 435$.

Triangular numbers

The numbers in the table, 1, 3, 6, 10, 15, 21, 28, are the triangular numbers: the numbers of dots you can arrange as a triangle, like the ten pins in bowling, or the staircase of Figure 11.1 with its corner smoothed. Each one is 1 + 2 + 3 + … up to some number, so the handshakes at a party of n are the triangular number that ends at n − 1.

Working backwards

At a reunion, someone counted 66 handshakes, everyone with everyone once. How many people were there?

Double it: 66 × 2 = 132. That is the number of people times one less than the number of people, two whole numbers next to each other. Which two neighbors multiply to 132? Try a few near the middle: 10 × 11 = 110, too small; 11 × 12 = 132. So there were 12 people. (Check: 12 × 11 ÷ 2 = 66.)

And not every number can be a count of handshakes. 100 handshakes would need two neighbors that multiply to 200, but 13 × 14 = 182 and 14 × 15 = 210. So nobody can ever count exactly 100 handshakes at a party where everyone shakes everyone’s hand.

Leagues

That last question shows something important. Halving was right for handshakes because a handshake between Gita and Bibek is the same as one between Bibek and Gita. When order matters, Gita’s team at home to Bibek’s is a different match from Bibek’s team at home to Gita’s, and nothing is counted twice.

The diagonals of a shape

A diagonal joins two corners of a shape that aren’t next to each other. How many diagonals does a hexagon have?

Every pair of corners is joined by a side or a diagonal. Six corners make 6 × 5 ÷ 2 = 15 pairs, and 6 of those pairs are the sides. So a hexagon has 15 − 6 = 9 diagonals (Figure 11.3).

Or count from each corner: a corner can’t join itself or its two neighbors, so it has 6 − 3 = 3 diagonals. Six corners, 3 each, is 18, and each diagonal has two ends: 18 ÷ 2 = 9. For a shape with n corners:

$$\text{diagonals} = \frac{n \times (n - 3)}{2}$$

A 30-sided shape has 30 × 27 ÷ 2 = 405 diagonals, just 30 fewer than the class’s 435 handshakes: the 30 sides.

Not everyone with everyone

The formula counts every pair. If some pairs don’t shake hands, count all the pairs, then take away the ones that don’t happen.

Cards, not handshakes

At Tihar, each of the 30 students in the class sends a card to every other student. How many cards are sent? It sounds like the handshake puzzle, but it isn’t: Gita’s card to Bibek and Bibek’s card to Gita are two cards. Nothing is counted twice, so there is nothing to halve: 30 × 29 = 870 cards. Before you halve, always ask: is the thing I’m counting the same from both ends?

When the handshakes are anyone’s choice

At a real party nobody makes a rule, and people shake hands with whoever they like. Then the total can be anything. But one thing is still always true. Try it:

However the hands are shaken, the number of amber people is even: 0, 2, 4 or 6, never 1, 3 or 5. The reason is Way 2 again: add up everyone’s count, and you get twice the number of handshakes, because each handshake gives two people one each. Twice anything is even. Now look at what makes up that even total. The even counts add up to an even number. Pair the odd counts off two at a time: each pair of odd numbers adds up to an even number. If one odd count were left over with no partner, it would make the whole total odd, and the total is even. So the odd counts always pair off exactly: there is an even number of them. This is called the handshake fact, and it is how Euler showed that the bridges of Königsberg can’t be walked: see Can You Cross Every Bridge Just Once?.

• How Many Number Plates Can a Province Make? Counting by multiplying, when the order does matter.
• How Many Ways Can You Walk to School? Counting routes along the lanes, and a triangle of numbers in which this topic’s numbers, 1, 3, 6, 10, 15, appear along a slanting line.
• Can You Cross Every Bridge Just Once? Dots and lines again, and why the handshake fact decides a walk.
• How Do You Schedule a League So Everyone Plays Everyone? (Grades 9–12) The 28 matches of an 8-team league fitted into rounds where nobody plays twice in a day.
• Must Two People Here Share a Birthday Month? (Grades 9–12) Another counting puzzle with a surprising answer.