翻译：蒋迅

原文出处：Handshake Lemma

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

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

Σ_p∈P d(p) = 2f

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

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

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

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

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

转载本文请联系原作者获取授权，同时请注明本文来自蒋迅科学网博客。

链接地址：https://wap.sciencenet.cn/blog-420554-1195255.html?mobile=1

收藏

分享