Question

一道数列问题

某天晚上21个人之间通了电话，有人发现这21人共通话102次，且每个两人至多通话一次，他还发现，存在M个人，第1个人与第2个人通了话，第2个人与第3个人通了话，......，第M-1个人与第M个人通了话，第M个人又与第1个人通了话，，他不肯透露M的具体值，只说M是奇数，求证：21个人中必存在3人，他们和同一个人通了话

Answer 1

证明：因为通话是相互的，所以命题“21人中必存在3人，他们和同一个人通了话”也就是“必存在1人和至少3人通了话”，它的反命题就是“21人中每个人至多只和2人通话”。下面就通过反证法来解答此题。
假设21人中每个人至多和2人通了电话。根据条件，已知存在的M个人通话可以形成一个圈，首尾相接。根据假设发现刚好其中每人都通了2次电话，所以这M个人不会再同其他任何人通话。
也就是说剩下的(21-M)人要通话(102-M)次。
在这些人中任挑一个通过电话的人编号为a1，和他通话的一人编号为a2。根据假设，每人至多通话2次，则a2最多还能跟1个人通话，如果有则编号a3，继续往下操作，直到某人通信中断为止；如果a2没有和其他人通话，则考察a1还跟第二个人通话没有，如果有，编号a3，继续操作，直到通信中断；否则这个链条只有a1-a2。
如此操作可以所有通过话的人分组成有限个链条组或者环形圈组，剩下的都是未通过话的，可以忽略不计。分析发现，凡是通过话的各组，内部通话次数总和最多的情况是环形圈，为该圈人数，否则即为链条组，通话次数为链条人数-1。所以，各组通话次数总不大于该组人数。
那么，所有通话的人，在假设每人最多通话2次的情况下，通话总次数不多于通话人数！！
而我们通过上面的分析，直到剩下的(21-M)个人需要通话(102-M)次，显然21-M<102-M，矛盾！！！
所以，21人忠必存在1人和至少3人通了话，也就是说21个人中必存在3人，他们和同1个人通了话。
证毕

这道题其实根本不需要知道M是什么数，甚至都可以不需要条件“已知存在M个人……”，只要知道共a个人通话了b次，a<b，每两人至多通话1次，那么结论a个人中至少三人和同一个人通了话显然就成立了。因为我们本身就是在构造“链”或者“圈”。此题应该不属于数列范畴，完全没用到任何数列知识，本质上更像属于图论题。希望学会举一反三。

Answer 2

用反证法。如果不存在3个人和同一人通话。
1）将人看作点，设集合A={M个人}，集合B={21中除了那M个人}
2）在集合A中的点，已经组成了一个环状。如果存在A中的一点(人)，和其他人通话，那就矛盾了。那么剩下的(102-M)次通话里，通话的两个人，必定在集合B里面。
3）而集合B中的点(人)，如果一个人与两个人通话，那么(21-M)个人，通了2(21-M)/2次。
如果通话次数多于（21-M）的话，那么就存在3个人和同一人通话了。
4）其实（102-M）必定大雨（21-M）的
5）所以必定矛盾，必定存在3人与同一人通话

追问

你好像也看错题了

Answer 3

证：用21个点表示21个人,若两人通电话则对应两点连一条边,构成图 .由已知, 中存在一个长度为 的奇圈.要证: 中存在三角形.
设图 中长度最短的奇圈为 ,长度为 .
若 ,则 为三角形.
若 ,设 为 ,则 与 之间无边( ),否则,若 与 相邻,则圈 与圈 长度之和为 ,故其中必然有一个长度小于 的奇圈,与 最短矛盾.
假设除 外的 个点无三角形,由Turan定理,它们至多连了 条边. 又其中任意一点不与 的相邻两点相邻(否则存在三角形),所以它至多与 中 个点相邻.
故总边数为
( ).
与图 共有102条边矛盾. 故图 中存在三角形,即存在三个人两两通话.

追问

你题目看错了，不是三个人互相通话，哈哈

追答

知道。题目跟你一样。QQ52946694，我告诉你

Answer 4

这不是数列问题，是图论问题。

用图论的语言重述此题：
简单图G=(V,E), |V|=21, |E|=102. 已知G中存在奇圈（长为奇数的圈）。证明存在一个顶点u, deg(u)≥3.
其中deg(u)表示u的度数，即以u为顶点的边的数目。

由简单图的基本定理，∑(u∈G) deg(u)=2|E|. 此命题很容易证，从顶点的角度计数G中的边数即可。
反设任意顶点u, deg(u)≤2. 由上式，左≤2*21<2*102=右，矛盾！
故结论成立！

P.S. 此题条件过强，“G中存在奇圈”的条件根本不需要，放缩也很松。
估计楼主的题有点问题，我见过一道竞赛题，条件相同，结论改为证明G中存在长为3的圈，这样才有意思~~