天空中的一个模式分享 http://blog.sciencenet.cn/u/jiangxun 本博将以数学杂文为主,科技杂文为辅,其它杂文为补。

博文

【数学应知道】握手引理

已有 1856 次阅读 2019-8-26 11:06 |个人分类:传数学|系统分类:教学心得| 数学都知道, 数学

翻译:蒋迅

原文出处:Handshake Lemma

问题:证明或否定:在一个有n个人的派对上,必存在偶数个人,他们有奇数个朋友。

解答:令P是所有人的集合,对每一个人 pP,令 d(p) 为此人的朋友的数目。令 f 为在派对上两两为朋友的的朋友对儿的总数。因为每一个朋友关系都正好涉及到在派对上的两个人,我们看到下式成立:

ΣpP d(p) = 2f

换句话说,每一个人得朋友数的和将正好是全部朋友关系的数目的和。特别地,这个数总是偶数。如果在派对上有奇数个人具有奇数个朋友,则总数 ΣpP d(p) 就只能是奇数了。

因此,在聚会上只有偶数个朋友可以有奇数个朋友。

讨论:这可以说是“双重计数”(double-counting) 的证明。双重计数通过显示相等的每一侧可以被认为是计算同一集合中元素的不同方式来证明等式。 在上面的证明中,我们用两种不同的方式来计算单方面友谊。

这种技巧遍及数学(特别是在组合学领域,与计算事物有关的数学领域)。我们可以通过将派对看作是一个图形来将它与图论相关联(见我们的非常基本的这个主题的介绍),其中顶点是人,边是朋友关系。於是,这个定理指出,对於任何图形,每个顶点的度数之和是边数的两倍,因此总是偶数。

加倍计数已被用来证明一些恒等式,它甚至可以用来证明像费马小定理一样有趣的东西(它有很多证明,而且有很多用途!)以及计算由一组 n 个不同顶点构成的树的数量(它很大:事实上是 O(nn) 呢!)。



http://blog.sciencenet.cn/blog-420554-1195255.html

上一篇:在外星人看来地球可能是这个样子
下一篇:有趣的三位数

4 杨正瓴 张江敏 徐传胜 李毅伟

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-11-12 04:03

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部