I was at a wedding on Saturday. It was a Catholic service, and as part of it, everyone was encouraged to bless their neighbor, including the grasping and waggling of hands.

I idly wondered how long it would take if we were required to do it not only with our immediate pewmates, but for everyone in the church. How many handshakes and blessings would be involved?

It turned out to be a simple problem, and one with a solution that wouldn't have kept us there until the wee hours, but it would certainly have added time to the service, if the logistics weren't well planned.

Say there were a hundred people in attendance. That meant that the first person would have to shake ninety-nine hands. The second person would only have to shake ninety eight, having already shaken the hand of the first person. Using the same logic, the third would only have to do ninety seven, and so on. Thus, by induction, the total number of palm pressings would be the sum of 1 through (N-1) where N is the number of wedding attendees.

So what is that sum for, say, N equal 101?

The obvious way to solve it is to simply start adding. But a seven year old boy once came up with a much faster way, when his entire grade-school class was tasked by a teacher who wanted to give them some busy work so she could get something else done. It makes it possible to do it in your head. The answer turns out to be 5050.

If you're interested in how he (and I) got it, click on the link for "More."

For those who came via permalink, there is no "More" link, so scroll down below for the answer instead.

********************************************

















Since N = 101, you have to sum the series 1 through 100.

Note that the numbers can be paired, thusly:

1, 100
2, 99
3, 98

and so on, up to (50, 51), yielding fifty such pairs.

Note also that each pair sums to 101.

So we've dramatically simplified the problem. Instead of adding a hundred numbers, we're reduced it to multiplying two numbers--50 times 101 yields the answer.

There's a general formula that will solve the problem.

Sum = (L + 1) * L/2, where L is the largest number. This applies only for even values of L. If it's odd, subtract one from L to make it even, do the formula on (L - 1), then add L back to it.

And, as Paul Harvey would say, here's the rest of the story. For those who aren't aware, that seven-year-old boy, Karl Friedrich Gauss, was one of the most brilliant mathematicians to ever live.

[Update at 3:40 PM PDT]

Sol Foster points out, correctly, in the comments section that the formula is valid for both even and odd numbers. I didn't bother to check the odd case. The reason that I thought that you had to adjust it for odds was in my derivation, because in the odd-number case, one of the numbers is missing a partner in the pairing. But apparently it's not a quantum effect--just use the formula for any L.

And to Sol, the reason that I had an N and an L was because in the application N was the number of wedding attendees, whereas L was the high number in the series.

The possibly apocryphal story of Karl Friedrich Gauss discovering this when he was 5 is where I first heard this one.
It seems Gauss was acting out in kindergarten one morning, and as a punishment his teacher asked him to add up the numbers from 1 to 100. As he started to add them, he discovered the pattern you alluded to in your entry, [(N+1)/2]*N, and he went back to the teacher, and told her the answer. The teacher, of course, had to add the numbers up herself to find out if he was right, turning the joke back on her (or him). Anyway, it is a nice, funny intro to series and sums

As you have no doubt surmised, I wrote that before clicking the "more" link, so my face is now as red as the (possibly apocryphal) teacher's.

Would you like me to delete the comment? ;-)

This ritual has been introduced to the Church of England too. Peter Hitchens calls it an "informal and intrusive rite of handhaking", and it was focibly introduced into traditional churches by the hierarchy as a way of downplaying the individual relationship with God that was a hallmark of English protestantism.

It strikes me that there might be an easy way for 100 people to shake hands relatively quickly. Line them up like a conga-line (without moving), then have the first person do a U-turn and shake the second person's hand, then the third, and so on, progressing down the line. The second person would do the same, having shook the first person's hand and now shaking the third person's hand, fourth person's, and so on. This continues at a quick pace until, finally, the last two people in line shake hands. From the air, it'd look like a centipede doing a tight U-turn and heading in the opposite direction.

That was your Useless Tip of the Day (TM). Thank you.

What I like is that the answer happens to be 5050. It reminded me of a colleague who, in what may have been a rare moment of candor regarding his analytic skills, said forcefully that:

"Hindsight is always 50/50!"

Regards,

What's this nonsense about the formula only applying to even values of L? It applies perfectly well to both even and odd values. If you want to avoid fractions, simply think of it as half of (L+1)*L.

Also, it's a bit weird that the question is stated in terms of N, but the answer given is in terms of L, where N=L+1.

I think it says something about having too much math training that instead of using the "pairing" solution, I wrote down a bunch of specific cases, dredged the formula up from memory that would fit them, and then proved it was right using induction.

Note that the numbers can be paired, thusly:

1, 100
2, 99
3, 98

and so on, up to (50, 51), yielding fifty such pairs.

Why/how do I know to stop at 50,51 if the sequence holds valid for 51,50; 52,49. I understand that it is probably something to do with unique pairs, but how would one know this?

Because if you go any farther, you'd be double counting, and get the wrong answer. You only want to count unique pairs.