Mathematics During Military Training — The Number of People Who Shake Hands an Odd Number of Times

军训中的数学——握手奇数次的人数 苏剑林 · 2012-09-22 · Mathematics number theory university graph theory

Military training is fairly tough, but there are always some boring moments in it. For instance, pretty much every time we assemble, the first thing we do is stand at attention — anywhere from five minutes to twenty or thirty minutes. During that stretch of time, your mind has to find something to occupy itself with, or else standing perfectly still becomes unbearable. I got through those boring moments of military training by thinking about math problems. Whenever I had a spare moment, my mind would drift to things like the series $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{p}$, the Goldbach conjecture, stability problems, and so on — not that I expected to make any great discovery, but just to pass the boring time, and also as a way of exercising my thinking and imagination.

As I mentioned before, yesterday our "combat formation" performed at the university town. On the way there, one of my "comrades-in-arms" asked me the following question:

In a crowd where people shake hands with each other, the number of people who have shaken hands an odd number of times is always even. Any two people may shake hands more than once.

He also said this question was posed by Einstein. That really got me interested. (Later, when I searched online, I couldn't find any connection between this problem and Einstein at all...) Below is my rather dramatic thought process.

The handshake problem in a crowd, more

First I imagined the n people as n points on a plane. Every time two people shook hands, I drew a line (not necessarily straight) connecting the two points, and thus obtained a picture. This immediately reminded me of the "Seven Bridges Problem" (of course, all of this was happening purely in my head, while riding in the car to the university town), and I felt that the two might be related. I came up with quite a few approaches — some based on basic graph theory, some on mathematical induction. Of these, the induction approach was the first one I actually worked out, so it became my first proof method.

Mathematical induction

My idea was this: in the picture above there are a number of lines (a segment connecting two points is called a line). Suppose the claim holds for a given configuration, and then consider what happens when one more line is added. This splits into several cases:

1. No new point is added. In this case the new line necessarily connects two of the existing points — it might join two people who had each shaken hands an odd number of times, two who had shaken hands an even number of times, or one of each. Examining these three sub-cases shows that none of them changes the number of people with an odd handshake count.
2. A new point is added. The case analysis here is similar to case 1, just organized slightly differently.
3. Two new points are added. This adds two people who have each shaken hands once (an odd number of times), which also doesn't change the parity of the count of people with an odd number of handshakes.

Putting these together, the original claim holds.

This line of reasoning proceeds step by step via induction; although it's complicated to describe in words, the argument felt quite obvious in my head as I was working through it, so I'll count it as one method I came up with. Later, when I looked at proofs online, I found that the induction there is usually carried out by going from n people to n+1 people, which is a different line of reasoning from mine.

The simplest method

But after our performance at the university town, thinking about it again, I felt that such a general problem (in particular, with no restriction on the number of people), stated so simply, ought to have a simple method that "grasps the whole picture." So I kept analyzing it. Since the problem is fundamentally about parity, my intuition was that the argument should set aside the number of people entirely. After a while, it suddenly dawned on me — the entire proof really amounts to just one sentence:

The total number of handshakes across all people is even (since each handshake between two people contributes two to the total handshake count), and the total contributed by the people who shook hands an even number of times is certainly also even. So what remains must come from the people who shook hands an odd number of times — and there must be an even number of them, otherwise we'd get the contradiction "odd + even = even."

A new line of thought?

Then in the evening there was a welcome party at school. Personally, I'm not much of a fan of watching performances, and with a lot of people standing in front of me, my view was basically blocked anyway. So rather than listen to the "radio," I figured I might as well keep thinking about this problem.

Even though the parity argument had cleverly solved the problem, I still felt that my original graph-theoretic idea couldn't be wrong — it should also admit some very simple graph-theoretic argument. So once again, points and lines began appearing in my mind. This line of thinking had actually started germinating that morning, only I'd abandoned it at first. Later I thought further and realized that, roughly speaking, every planar figure can be decomposed into a number of closed curves and open curves — in simple terms, every figure can be broken down into some number of loops and some number of lines. In the picture above, if we remove all the connecting lines that form loops, this doesn't change the number of people with an odd handshake count. Repeating this operation eventually leaves only a number of lines and a number of isolated points, with no loops remaining; and each line has exactly two people at its ends who each shook hands an odd number of times (namely once). So that counts as another small proof.

……

I didn't keep thinking about it any further today — I wonder if any readers out there have simpler or more interesting ideas? Today was a rare day off, so I went for a walk with some classmates instead and didn't have time to think about it further. Perhaps at some other boring moment I'll come back to it, and something new will occur to me — but that's a story for another time. University life: classes, thinking, research...