November 13th, 2012

On Tuesday, November 13th, we returned to a previous problem and then explored it more deeply, eventually doing a physical demonstration that led to some new questions. The original problem, commonly known as the "Handshake Problem," asks students to consider a party with 100 people at which every person shakes hands with every other person one time, and then to determine how many handshakes there are in total.

One of the problem-solving methods students are asked to employ is to simplify problems with "inconvenient" or "unwieldy" numbers by using easier or smaller numbers, trying to discover an underlying pattern or principle, and then applying that to the original situation. In the Handshake Problem, I intentionally make the number of guests large so that simply counting will be tedious and impractical. This is intended to push students to try to model the problem with a more manageable number of guests, such as five. If need be, I ask leading questions until someone realizes that 100 is too large to model. Most students (no matter what age group I do this problem with) initially guess that the answer will be either 100*100 or, after some thought, 100*99, which, while more reasonable, is still much too large. Some students argue, correctly, that the first person has to shake hands with 99 others, the next person with 98 others (having already shaken hands with the first person), and so on until the last person doesn't need to shake hands with anyone, having shaken hands will all the other 99 guests. Thus, we can get the answer by adding the whole numbers from 1 to 99. This is an improvement, but still requires a tedious calculation. So we try to see if there is a quick way to add consecutive whole numbers from, say, 1 to n.

I generally introduce the (possibly apocryphal) story about the young Karl Gauss (generally viewed as one of the greatest mathematicians of all time), who added all the whole numbers from 1 to 100 by arguing that he could write 1 2 3 . . . 98 99 100 and then write directly under them 100 99 98 . . . 3 2 1. Adding the two rows would result in 100 copies of 101. However, he noted, 100*101 would be the sum of the numbers from 1 to 100 TWICE. So the right answer would have to be 50*101 = 5050 (which is correct), and in general the formula here would be[n(n + 1)]/2, which the division by 2 represents adjusting for "double counting").

Looking back at the handshake problem with this analysis suggests the fast way to solve the problem. The first person must shake hands with 99 others. And all 100 people are in the same boat. That is where 100*99 comes from. However, when A shakes hands with B, B is simultaneously shaking hands with A. That is only ONE handshake, but each person counts it. So we have double-counting again. Thus, the correct answer is 100*99/2 or 50*99. The general formula for the handshake problem is [n(n - 1)]/2, similar but not identical to the formula Gauss (and countless others since him) derived.

We then looked at related problems where a new parameter for repetitions - k - is introduced. This would come into play, for example, where we had 10 basketball teams in a league where each team played the others 4 times during the season. The calculation would be (10*9*4)/2 and the general formula would be
[n*(n-1)*k]/2

Finally, I raised the question of whether in these sorts of problem, the second factor would always be n - 1. Would it be possible to have [n*(n - a)*k]/2 for a = 2 or 3 or some other number?

I posed the following: given an octagon, how many diagonals must be drawn to connect all the vertices to those vertices to which they are not already connected?  Students generally realized that in this case, a could not equal 1. Most of them switched their focus to the two vertices adjacent to any given vertex, and decided that the correct equation was (8*6)/2 = 24. However, a careful count of the total diagonals (keeping in mind that the sides of the octagon do not get counted), revealed that the correct total is 20. Where had they gone wrong? They had forgotten that any given vertex does not get a diagonal drawn to itself. Thus, a = 3, not 2, and the correct equation here is (8*5)/2 = 20 and the formula would be [n*(n-3)]/2.

The class then took surveyor's tape to model the problem and to explore an interesting algorithm. First, a group of 5 students formed a rough pentagon. One student wrapped the tape around his left wrist and passed it to the student on his left. This repeated until we had the sides of the pentagon. Then, the first student wrapped his left wrist again and the tape was passed to every 2nd student until it came back to the first student again (this took two circuits around the pentagon). At this point, we saw that there was a pentagram (5-pointed star) inside our figure and that everyone was connected by one diagonal to everyone else except for himself and his adjacent neighbors (see photo)

A complete graph on 5 vertices

Next, a group of seven students followed a similar process, but after the two circuits that had them passing to every second student, we had to make three circuits passing to every third student before every diagonal was completed (see photo)

A complete graph on 7 vertices

Finally, we tried this process with six students. Everyone was surprised to discover that the method didn't work: after one circuit passing to ever second student, they were stuck in a triangle that never released to the other three students!

We ended class with Stanley conjecturing that this method would never work for an even number of vertices. I asked students to consider for tomorrow what numbers would and would not work for this particular method of connecting all the diagonals and sides (edges).