order, the combined (double) sum may be computed easily by first adding the pairs of numbers aligned vertically and then adding horizontally. As can be seen below, each vertical sum is 101, and there are exactly 100 of them. So the double sum is 100×101, or 10,100, which means that the desired sum is half that, or 5050.

For the original handshake problem, which involves the sum of the blocks in the staircase above, that means taking the double sum 7×8, or 56, and halving it to get 28.

The handshake problem can be approached by bringing in ideas from other parts of mathematics. If the people are thought of as standing at the vertices of an eight-sided figure (octagon), then the question again becomes geometric but in a different way: How many segments (sides and diagonals) may be drawn between vertices of an octagon? The answer again is 28, as can be verified in the picture below.

As often happens in mathematics, connections to geometry provide a new way of approaching the problem: Each vertex is an endpoint for exactly 7 segments, and there are 8 vertices, which sounds like there ought to be 7×8=56 segments. But that multiplication counts each segment twice (once for each endpoint), so there are really half as many, or 28, segments.

In still another mathematical domain, combinatorics—the study of counting, grouping, and arranging a finite number of elements in a collection—the

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement