#handshake problem

This is a really good problem for looking at through the lens of patterns.

With 1 person, there are no handshakes.

Between two people, there is one, just between the two.

For three handshakes between Alice, Bob and Carol, Alice shakes both Bob and Carol’s hand (that’s two) and then Bob and Carol need to shake hands. So that’s 3. 

Four handshakes: A, B, C, D. A shakes everyone’s hand (3). Then B has to shake C and D’s hand, but *not* A’s because they already shook. So that’s two more, and then C and D shake. That’s 6 in total.

We could run through five handshakes, or we could imagine that A, B, C and D have already done all their handshaking, and then E walks into the room. What happens? Ze shakes everyone’s hand in the room, which is 4 more. So that’s 10.

The next person has five hands to shake, so that’s 15.

So our pattern is:

0, 0+1, 0+1+2, 0+1+2+3, 0+1+2+3+4, 0+1+2+3+4+5 and so on.

So how many handshakes occur between and among 10 people? Well, the first person has to shake 9 hands, the next person 8, and so on. So 9+8+7+6+5+4+3+2+1=45.

Triangle Numbers

These are called the triangle numbers, because you can make increasing sizes of triangles like this, with each row having one more dot.

Consider, though, that in a group of 10, every person shakes 9 hands. So why aren’t there 90 handshakes? (Think about it)

Well, when two people shake hands, they both come away thinking there’s been a handshake, so there are two handshakes accounted for in the count. Each handshake is double counted, so there are 90/2=45 handshakes.

And this gives us a method for finding the number of handshakes among 100 people. It’s 100*99/2=4950. Or n people: n(n-1)/2.

This is just a bit off of the nth triangular number, because for triangular numbers, we don’t count 0 as the first, with one person. So the 100th triangular number is the number of handshakes among 101 people.

And we get a slightly different equation, which we can derive algebraically, or geometrically, which is cool. Take one of the above triangles, left justify it, double it and put them together to make a rectangle:

The area of the rectangle is n(n+1) and we divide it by two to get the area of the triangle, n(n+1)/2.

Other Problems

Diagonals: How many diagonals does an n-gon have? Go try and find a pattern!

A triangle has no diagonals. A quadrilateral has two. A pentagon has five. A hexagon has nine. 

0, 2, 5, 9. Looks like we add two, then three, then four. Why would that be?

Well, let’s look at a pentagon. There are five diagonals already. If we add a corner, what connects to that? This is our 6th corner, and it can’t connect to itself, nor to those corners directly adjacent to it. So it has three dots to connect to, adding three diagonals. But ALSO, one of the sides of our original pentagon is no longer a side, but a diagonal. This is probably best seen in pictures:

You see the original on the left, and then the new sides (in green) and the new diagonals (in purple), including IH, which was a side (DC) in the original.

What would happen next? The 7th corner will connect to four (7-itself-two adjacents=4) diagonals, and there will be another side turning into a diagonal. So 9+5=14.

So how many for a 10-gon? Well let’s recap:

3-gon (triangle): 0

4-gon (quadrilateral): 2

5-gon (pentagon): 5 (2+3)

6-gon (hexagon): 9 (2+3+4)

7-gon (heptagon): 14: (2+3+4+5)

So it looks like 10-gon would be: 8 (start at 2 less than the number of sides) +7+6+5+4+3+2 (don’t include 1) = 35.

If you notice, we have the triangle numbers minus 1, because of no shape with only 1 diagonal.

Equation

Is there a faster way, like for the triangle numbers? Well, of course you could just do the triangle numbers minus 1, but being careful about which triangle number we’re at, because we start at n=3, with a triangle, because the first triangle number (1) minus 1 =0. So we have to subtract two from our n’s.

So we could do (n-2)(n-1)/2 - 1. Let’s test to see if I’ve done it right.

For n=3: (1)(2)/2 - 1=0. Good!

Or n=10: (8)(9)/2 - 1 =35. Great.

OR, look for another pattern like the handshakes. Every corner (n) connects to every other one, except itself and the two next to it (n-3).

That’s n(n-3). But again, every line connecting two dots/corners is going to be counted twice, A to B and then B to A. So n(n-3)/2.

Again: for n=3, we get 0.

For n=10: 10(7)/2=35.