Let's Shake on That!

Here's another puzzle that explores the world of functions.

Ramanujan is having a party. Since his father and mother named him after a famous Indian mathematician of the 20th century, Srinivasa Ramanujan, he always likes to have mathematical puzzles at his parties. His friends call him Rama for short. In his invitation he wrote:

Challenge 1

If everyone shakes hands with everyone exactly once, 153 handshakes will take place. Can you explain why?

At the party, Rama asked his friends to solve two other puzzles.

Challenge 2

Find a rule telling how many handshakes will take place among any number of people, N, if each person shakes everyone else's hand once.

Challenge 3

If you draw a polygon with N sides, and then draw all the possible diagonals, how many line segments will you draw? How does this result relate to the number of handshakes for N people?

Background

This puzzle, like others in the Algebraic Thinking category, deals with a function. Remember that in mathematicsspeak a function is a rule relating two variables, so that if you know one of the variables, called the independent variable, the rule tells you the value of the other variable, the dependent variable.

In Building With Bricks our puzzle involved "square numbers," the series 1, 4, 9, 16, 25, and so forth. In Painting Cubes we investigated "cube numbers," the series 1, 8, 27, 64, 125, and so forth. This time our pattern results in another famous series called "triangle numbers."

You may want to look up information about Srinivasa Ramanujan [1] on the Web. A BBC movie is being made about his life. There is even a rock song about his life.

Hints:

Since this puzzle involves a function, you can approach it either inductively, starting from the simplest case and looking for a pattern, or deductively, by thinking about the general case and using reasoning to find a solution for N people.
Some people find that making a drawing can help them solve this type of puzzle.

Course:

Math [2]
Algebra [3]

Result/Solution(s)

Solution: Let’s Shake on That! Math Puzzle

As usual there is not just one way to solve these puzzles. Rama and two of his friends went about the problem in different ways.

Ramanujan's Solution

Algebra is my friend. I like to try to find a solution for N people first and then make sure that it works for a specific number of people. I figured that if there are N people at the party, each one shakes hands with N – 1 people. So the total number of handshakes must be:

N persons x (N - 1) handshakes / person or N x (N - 1) handshakes

But this can’t be right. Because if I shake hands with you, then I can’t count it as a handshake for you. Since every handshake involves two people, the total has to be divided in half.

So H = N (N - 1) / 2. For myself plus 17 guests that’s 18 x 17 / 2 = 9 x 17 = 153.

The number will always be odd because either N or N - 1 will be an odd number, and multiplying an odd number by anything is always odd.

This takes care of Challenges 1, 2, and 3. Now for a new challenge, Challenge 4:

Suppose I draw a polygon with N sides and connect each vertex to every other vertex. For example, in the sketch to the right point A is connected to every other point: B, C, D . . . through H. This polygon has 8 sides, and A is connected to the other 7 vertices.

If I draw all the diagonals, point B will also be connected to 7 vertices; so will point C, and so forth.

If the polygon had N sides, each vertex would be connected to every other vertex, that is, N - 1 vertices. So there would be N x N - 1 line segments. However, the line from A to C, for example, is the same as the line from C to A. So if I go with my first calculation, each line will be counted twice. So I divide the total by 2 to get N (N - 1) / 2 which is exactly the same as the number of handshakes for N people.

At first this surprised me—but when I tried drawing a picture to illustrate the handshake problem, I realized that every dot is like a person and the lines joining A to B, A to C, and so forth, could represent handshakes. Person A shakes hands with everyone else around the room, N – 1 of them, which is the same as the number of vertices connected to point A in an N-sided polygon.

So the polygon is like a picture or model of the handshake problem. That’s why they have the same result.

Juanita's Solution

I imagine that I come to the party first and shake hands with Rama. That’s 2 people and 1 handshake.

Then Ilya comes in. Rama and I both shake hands with him. That’s 3 people and 2 more handshakes.

Then Henrique comes in. He shakes hands with Ilya, Rama, and me. That makes 4 people and 3 more handshakes. I’m starting to see a pattern. When the Nth person comes in, he or she shakes hands with N - 1 people who are already there.

I started making a table.

Number of People	Number of New Handshakes When Person Arrives	Total Number of Handshakes
2	1	1
3	2	3
4	3	6
5	4	10
6	5	15

I could keep doing this until the 17th person arrives, but that would be boring. I think I see a pattern. The total number of handshakes is one-half the product of the number of people times 1 less than the number of people. Using algebra:

1 / 2 x N x (N - 1)

I checked it and it works for every case. So for 17 people invited, that’s 18 people all together including Ramanujan. So the total number of handshakes is

1 / 2 x 18 x 17 = 9 x 17 = 153. So I proved it.

I solved the polygon problem the same way. I drew a bunch of polygons with 3, 4, 5, and 6 sides, counted all the line segments, and made a table. (There’s no such thing as a 2-sided polygon.)

Polygon	Number of Sides	Number of Line Segments
	3	3
	4	6
	5	10
	6	15

The pattern is exactly the same as for the handshakes. If N is the number of sides, then the total number of line segments is N x (N-1) / 2.

Ilya's Solution

I started solving the problem the way that Juanita did. I figured out how many handshakes there are for 2, 3, 4, 5, and 6 people. But when I made my table, I found a different kind of pattern.

Number of People	Number of New Handshakes When Person Arrives	Total Number of Handshakes	Number of Handshakes as a Sum
2	1	1	0 + 1
3	2	3	1 + 2
4	3	6	1 + 2 + 3
5	4	10	1 + 2 + 3 + 4
6	5	15	1 + 2 + 3 + 4 + 5

The pattern I noticed is that the total number of handshakes is equal to the sum of all the previous numbers of people.

For N people, the number of handshakes is the sum of all numbers up to N + 1. I used Gauss’s method for finding that sum. You list all the numbers, then reverse the list, add the two lists, and take half.

        1   +   2 +      3 + . . . + N - 3 + N - 2 + N - 1

+

        N - 1 + N - 2 + N - 3 + . . .   3 +    2 +      1

=      N   + N + N + . . .     + N + N + N

This is the same as adding N to itself N - 1 times, or N (N - 1). When I take half of this double sum, I get N (N - 1) / 2.

This is the same as what Rama and Juanita got. Just like Juanita, I got exactly the same pattern when I explored the number of line segments in a polygon.