Military training is quite exhausting, but there are always some boring moments. For example, the first thing we do after every assembly is basically standing at attention—sometimes for as little as five minutes, other times for as long as twenty or thirty minutes. During this time, the mind must find something to think about; otherwise, staying completely still is very difficult to endure. I spent those boring moments of military training by thinking about mathematical problems. For instance, whenever I had free time, my mind would drift to topics like the series \frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\dots+\frac{1}{p}, the Goldbach conjecture, stability problems, and so on. It wasn’t that I expected to make any great discoveries; it was simply to pass the time and to exercise my thinking and imagination.
As mentioned before, yesterday our "Combat Phalanx" went to University City for a performance. On the way there, one of my "comrades-in-arms" asked me the following question:
In a group of people shaking hands with each other, there is always an even number of people who have shaken hands an odd number of times. Any two people can shake hands more than once.
He also mentioned that this was a question posed by Einstein. This immediately piqued my interest. (Later, I searched online but couldn’t find any connection between this problem and Einstein...) Below is my rather dramatic thinking process.
First, I imagined representing n people as n points on a plane. If two people shake hands once, a line (not necessarily straight) is drawn between the two points, resulting in a graph. This immediately reminded me of the "Seven Bridges of Königsberg" problem (all of this was done in my head while on the bus to University City), and I felt there might be a connection. I devised several methods, including basic graph theory and mathematical induction. The inductive method was the first proof I constructed.
Mathematical Induction
My idea was as follows: suppose there are several lines in the graph (a line connecting two points represents a handshake). Assume the proposition holds in this state, and then study the case of adding one more line. This can be divided into several scenarios:
No new points are added: The new line must be placed between two existing points. These could be two people who have shaken hands an odd number of times, two who have shaken hands an even number of times, or one of each. By discussing these three cases, one can see that the parity of the number of people with an odd number of handshakes does not change.
One new point is added: This scenario is similar to the first, just with a different method of discussion.
Two new points are added: This adds two people who have shaken hands an odd number of times (exactly once), which also does not change the parity of the total count of "odd-handshakers."
In summary, the original proposition holds.
This line of reasoning uses mathematical induction to prove the statement step-by-step. Although it sounds complex to describe, the logic was quite obvious when I was reasoning it out in my head, so I consider it one of my methods. Later, I looked at proofs online and found that mathematical induction is often done by moving from n people to n+1 people, which is a different approach from mine.
The Simplest Method
However, after the military training performance, I thought further. Such a universal problem (with no limit on the number of people) and such a simple description should have a simple "global" method of proof. So, I continued to analyze it. Since the problem concerns parity, I had an intuition that I should set aside the specific number of people. After a while, it dawned on me—the entire proof can be summarized in one sentence:
The total number of handshakes across all people is even (because each handshake between two people generates two "handshake counts"), and the sum of handshakes for those who have shaken hands an even number of times is certainly even; therefore, the remaining sum (from those who have shaken hands an odd number of times) must be even, which means there must be an even number of such people, otherwise we would have a contradiction of "odd + even = even."
A New Line of Thought?
That evening, there was a freshman welcoming party at the school. Personally, I don’t particularly enjoy watching performances, and since many people were standing in front of me blocking my view, I figured I might as well think about math problems rather than just listening to the "radio." So, I continued to ponder this problem.
Although the parity analysis solved the problem elegantly, I felt my initial graph theory intuition wasn’t wrong; there should be a very simple graph-theoretic demonstration. Thus, points and lines continued to appear in my mind. This idea had sprouted in the morning but was initially abandoned. Later, I thought: It seems every planar graph is composed of several closed curves and non-closed curves. Simply put, every graph can be divided into several cycles and several paths. In the graph above, if we remove the lines that form cycles, it does not change the parity of the number of people with odd handshakes. By repeating this operation, we are eventually left with several paths and isolated points, with no cycles remaining. Since every path has exactly two endpoints (representing two people with an odd number of handshakes, i.e., degree one), this serves as another small proof.
......
I didn’t continue thinking about it today. I wonder if any readers have simpler or more interesting ideas? It was a rare day off today, so I spent some time walking around with classmates and didn’t have much time to think. Perhaps in some future boring moment, I will continue to reflect on it, and some new ideas might emerge, but that is a story for another time. University life: classes, thinking, research...
When reposting, please include the original address: https://kexue.fm/archives/1713
For more details on reposting, please refer to: Scientific Space FAQ