军训中的数学——握手奇数次的人数
By 苏剑林 | 2012-09-22 | 26575位读者 |军训是比较辛苦,可是总有一些无聊的时刻。比如我们每次集合后的第一件事基本上都是站军姿,少则五分钟,长则二三十分钟,在这段时间里,头脑总得找点东西想才行,不然一动不动的,非常难熬。我就是在军训那些无聊的时刻里通过想数学问题来度过的。比如一有空余时间,我的头脑就浮现着级数$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{p}$、哥德巴赫猜想、稳定性问题啦等等,并不是说要做出什么大发现,只是为了渡过无聊时间,也是对自己的思维能力和想象能力的锻炼吧。
之前提到过,昨天我们的“格斗方阵”去大学城表演了。在去大学城的过程中,我的一位“战友”问了我一个这样的问题:
在一个相互握手的人群中,握手奇数次的人总是有偶数个。每两个人可以握多于一次的手
他还说这是爱因斯坦提问的。这可把我的兴致给调动起来了。(后来我在网上搜索,却发现不了这个问题跟爱因斯坦的任何联系...)下边是我的颇有戏剧性的思考过程。
首先我设想把n个人看成平面上的n个点,两个人握过一次手,就在两个点之间连一条线(不一定是直线),然后就得到了一幅图画了。这不禁让我联想到了“七桥问题”(当然这一切都是在头脑中完成的,那时候在坐车去大学城),感觉两者会有一点联系。我构思了不少方法,有图论基本的,有数学归纳的,其中数学归纳法是构思出来了,这是我想出的第一个证明的方法。
数学归纳法
我的想法是这样的,上面的图像中有若干条线(两个点之间的连线称之为一条线),假设在此情况下成立,然后研究多添加一条线的情况,但这又分为几种情况:
1、没有增加新的点,这样这条新线必然是搭在原来的那些点的其中两个点之间的,也许是两个奇数次握手人之间,也许是两个偶数的,也许是一奇一偶,分别讨论这三种情况,可以发现都没有改变原来的奇数次握手的人数;
2、增加了一个新的点,这样分的情况类似第一种情况,只是讨论的方式不同而已;
3、增加了两个点,这样就是增加了两个奇数次(一次)握手的人,也没有改变原来的奇数次握手的人数的奇偶性。
综上,原命题成立。
这样的思路是通过数学归纳法一步步证明,虽然描述起来很复杂,但是在我的头脑中论证的时候是很显然的思路,所以这也算是我想到的一种方法吧。后来我看了网络的证明,数学归纳法是通过从n个人到n+1个人那样论证的,思路不同于我的。
最简单的方法
但是我在军训表演完后再想,这样的一个普遍性(主要是没有人数的限制)、描述如此简单的问题,应该有一个能够“把握全局”的简单方法才对,于是我就继续分析它。由于问题论证的是奇偶性,所以我有一个直觉就是应该抛开人数来论证。一阵子之后,我恍然大悟,原来整个证明只有一句话:
所有人的总握手次数是偶数(因为两个人握一次手就产生了两次握手数),而那些握手偶数次的人的总握手次数肯定是偶数,那么剩下的是握手奇数次的人,他们只能是偶数个,不然会出现“奇+偶=偶”的矛盾情况。
有一种新的思路?
然后晚上是学校的一个迎新晚会。就我个人来讲,我是不大喜欢看表演的,而且前边很多人站着,基本上把我的视线挡住了,与其在听“收音机”,倒不如想想数学问题,所以我就继续思考这个问题。
虽然通过奇偶分析很巧妙地解决了这个问题,但是我感觉我一开始的图论思路应该不会错的,它应该也有着一种图论方面的很简单的论证方法。于是我的头脑中继续出现了一个个点和一条条线。这个思路在早上的时候就萌芽了,只是一开始放弃了,后来我继续想到,似乎每个平面图形都是有若干段封闭曲线和非封闭曲线组成,简单来讲,每个图形都可以分为几个环和几条线。在上面的图形中,若是让可以构成环的连线都消失的话,是不改变奇数次握手的人数的,重复这样的操作,最终只会剩下若干条线和若干个单独的点,而没有环的;而每一条线都是有偶数个奇数次(就是一次)握手的人的,这样也算是一个小证明吧。
......
今天也没有继续思考下去了,不知道各位网友还有没有一些更简单或更有趣的想法呢?今天难得休息,就找了一些同学一起走了一下,也没有时间去想了。也许在某个无聊的时刻,我会继续思考它,会有一些新的玩意冒出来,不过那是后话了。大学生活,上课、思考、研究......
转载到请包括本文地址:https://spaces.ac.cn/archives/1713
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 22, 2012). 《军训中的数学——握手奇数次的人数 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/1713
@online{kexuefm-1713,
title={军训中的数学——握手奇数次的人数},
author={苏剑林},
year={2012},
month={Sep},
url={\url{https://spaces.ac.cn/archives/1713}},
}
January 13th, 2018
您好,“若是让可以构成环的连线都消失的话,是不改变奇数次握手的人数的”这个结论或许不是很正确:如,考虑两个有一条公共边的环,除去后奇数次握手的人数是变的,虽然奇偶性没变
抱歉,可能是我想错了,可以只除去一个环再剩一条线